oj.uz

Submission #245101

# Submission time Handle Problem Language Result Execution time Memory
245101 2020-07-05T13:32:35 Z Tc14 Political Development (BOI17_politicaldevelopment) C++17
23 / 100
 3000 ms 5496 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;

const int MAXN = 50000;

int r;
ve<int> G[MAXN];
ve<int> S;

bool disagree(int a, int b) {
    for (int i : G[a]) {
        if (i == b) return true;
    }
    return false;
}

void f(int a, int i, int d, int s) {

    bool valid;

    if (i == d) r = max(r, s);
    else {
        f(a, i + 1, d, s);

        valid = true;
        for (int j = 0; j < s; j++) {
            if (!disagree(S[j], G[a][i]) || !disagree(G[a][i], S[j])) {
                valid = false;
                break;
            }
        }

        if (valid) {
            S.push_back(G[a][i]);
            f(a, i + 1, d, s + 1);
            S.pop_back();
        }
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, d, a;

    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> d;
        for (int j = 0; j < d; j++) {
            cin >> a;
            if (a != i) G[i].push_back(a);
        }
    }

    r = 1;
    for (int i = 0; i < n; i++) {
        S = {i};
        f(i, 0, G[i].size(), 1);
    }

    cout << r << endl;

    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 7 ms 1664 KB Output is correct
4 Execution timed out 3072 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 7 ms 1664 KB Output is correct
4 Execution timed out 3072 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1664 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 5 ms 1536 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 156 ms 5368 KB Output is correct
12 Correct 5 ms 1536 KB Output is correct
13 Correct 158 ms 5368 KB Output is correct
14 Correct 6 ms 1536 KB Output is correct
15 Correct 165 ms 5368 KB Output is correct
16 Correct 158 ms 5496 KB Output is correct
17 Correct 166 ms 5368 KB Output is correct
18 Correct 175 ms 5368 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 7 ms 1664 KB Output is correct
4 Execution timed out 3072 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 7 ms 1664 KB Output is correct
4 Execution timed out 3072 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -