Rezultati

Up. imeNalogaJezikRezultatČas oddaje
qubit-2017 Škatle C++ 100/100OK 20. apr '17 @ 17:58

Test Točke Porabljen spomin Porabljen čas Status
#1 6/6 3,133 MiB 0,004 s OK
#2 6/6 3,203 MiB 0,010 s OK
#3 6/6 3,211 MiB 0,004 s OK
#4 6/6 3,211 MiB 0,004 s OK
#5 6/6 3,207 MiB 0,004 s OK
#6 7/7 3,211 MiB 0,004 s OK
#7 7/7 3,145 MiB 0,004 s OK
#8 7/7 3,203 MiB 0,004 s OK
#9 7/7 3,141 MiB 0,004 s OK
#10 7/7 3,219 MiB 0,010 s OK
#11 7/7 3,215 MiB 0,010 s OK
#12 7/7 3,184 MiB 0,053 s OK
#13 7/7 3,254 MiB 0,077 s OK
#14 7/7 3,227 MiB 0,217 s OK
#15 7/7 3,219 MiB 0,108 s OK

Ocenjevani program (n6.cpp):
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>

typedef long long ll;

using namespace std;

bool pase(vector<int>& out, vector<int>& in, int d) {
    vector<bool> vis(d, false);
    for (int zun : out) {
        for (int i = d - 1; i >= 0; i--) {
            if (!vis[i] && in[i] < zun) {
                vis[i] = true;
                break;
            }
            if (i == 0) {
                return false;
            }
        }
    }
    return true;
}

int dfs(int id, int n, vector<vector<bool>> p, vector<int>& memo) {
    if (memo[id] != -1) return memo[id];
    int maxlen = 0;
    for (int i = 0; i < n; i++) {
        if (p[id][i]) {
            int temp = dfs(i, n, p, memo);
            if (temp > maxlen) maxlen = temp;
        }
    }
    memo[id] = maxlen + 1;
    return maxlen + 1;
}

int main(void) {
    cin.tie(nullptr);
    cin.sync_with_stdio(false);

    int n, d;
    cin >> n >> d;
    vector<vector<int>> xs(n, vector<int>(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> xs[i][j];
        }
        sort(xs[i].begin(), xs[i].end());
    }
    vector<vector<bool>> povezave(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                povezave[i][j] = pase(xs[i], xs[j], d);
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << (povezave[i][j] ? 1 : 0) << (j == n - 1 ? '\n' : ' ');
    //     }
    // }
    vector<int> roots;
    for (int i = 0; i < n; i++) {
        bool root = true;
        for (int j = 0; j < n; j++) {
            if (povezave[j][i]) {
                root = false;
                break;
            }
        }
        if (root) {
            roots.push_back(i);
            //cout << i << endl;
        }
    }
    int maxlen = 0;
    vector<int> memo(n, -1);
    for (int id : roots) {
        int temp = dfs(id, n, povezave, memo);
        if (temp > maxlen) maxlen = temp;
    }
    cout << maxlen << '\n';

    return 0;
}