oj.uz

Submission #439526

# Submission time Handle Problem Language Result Execution time Memory
439526 2021-06-30T07:43:58 Z K4YAN Political Development (BOI17_politicaldevelopment) C++17
16 / 100
 3000 ms 40312 KB 
//Be Name Khoda
// 10:55 -> 10:50 shoroo
// 12:05 | 12:05

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define plll pair<pll, ll>
#define piii pair<pii, int>
#define piiii pair<pii, pii>

const int mxn = 5e3 + 5;
int n, k, q, v, w;
vector<int> dp[mxn][11], kmk;
vector<vector<int>> g[11];
bool edge[mxn][mxn];

void input() {

    int tmp = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> q;
        for(int j = 0; j < q; j++) {
            cin >> v;
            edge[v][i] = edge[i][v] = 1;
            if(i < v) {
                dp[i][2].push_back(tmp);
                dp[v][2].push_back(tmp++);
                g[2].push_back({i, v});
            }
        }
    }

}

void solve() {

    for(int i = 3; i <= k; i++) {
        int tmp = 0;

        for(int j = 0; j < n; j++) {

            for(auto u : g[i - 1]) {

                bool b = true;
                for(auto e : u) {

                    if(edge[j][e] == false) {
                        b = false;
                        break;
                    }

                }

                if(b == false) {
                    continue;
                }
                for(auto e : u) {
                    kmk.push_back(e);
                    dp[e][i].push_back(tmp);
                }
                dp[j][i].push_back(tmp++);
                kmk.push_back(j);
                g[i].push_back(kmk);
                kmk.clear();
            }
        }
        if(int(g[i].size()) == 0) {
            break;
        }
    }

    for(int i = 2; i <= k; i++) {
        if(int(g[i].size()) == 0) {
            cout << i - 1 << endl;
            return;
        }
    }
    cout << k << endl;
    return;

}

int main() {

    ios_base::sync_with_stdio(false);

    input(), solve();

    return 0;

}
/*
5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 15 ms 23096 KB Output is correct
4 Correct 13 ms 22116 KB Output is correct
5 Correct 14 ms 22176 KB Output is correct
6 Correct 12 ms 19808 KB Output is correct
7 Correct 14 ms 20104 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 1 ms 1612 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 15 ms 23096 KB Output is correct
4 Correct 13 ms 22116 KB Output is correct
5 Correct 14 ms 22176 KB Output is correct
6 Correct 12 ms 19808 KB Output is correct
7 Correct 14 ms 20104 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 1 ms 1612 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 13 ms 22172 KB Output is correct
12 Correct 783 ms 22164 KB Output is correct
13 Correct 1 ms 1612 KB Output is correct
14 Correct 800 ms 22168 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 760 ms 20100 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 768 ms 19808 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 392 ms 19640 KB Output is correct
21 Correct 387 ms 19660 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 967 ms 24572 KB Output is correct
24 Correct 5 ms 1612 KB Output is correct
25 Correct 975 ms 24804 KB Output is correct
26 Correct 855 ms 23876 KB Output is correct
27 Correct 756 ms 24652 KB Output is correct
28 Correct 860 ms 23700 KB Output is correct
29 Correct 779 ms 24720 KB Output is correct
30 Correct 1055 ms 24176 KB Output is correct
31 Correct 1014 ms 25520 KB Output is correct
32 Correct 1024 ms 24456 KB Output is correct
33 Correct 1034 ms 25520 KB Output is correct
34 Correct 1008 ms 25448 KB Output is correct
35 Correct 263 ms 13516 KB Output is correct
36 Correct 256 ms 13492 KB Output is correct
37 Correct 256 ms 13516 KB Output is correct
38 Correct 95 ms 7244 KB Output is correct
39 Correct 96 ms 7432 KB Output is correct
40 Correct 1583 ms 26384 KB Output is correct
41 Correct 97 ms 7300 KB Output is correct
42 Correct 1579 ms 26184 KB Output is correct
43 Correct 1544 ms 26348 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct
8 Correct 1 ms 1612 KB Output is correct
9 Correct 1 ms 1612 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Runtime error 4 ms 3020 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 15 ms 23096 KB Output is correct
4 Correct 13 ms 22116 KB Output is correct
5 Correct 14 ms 22176 KB Output is correct
6 Correct 12 ms 19808 KB Output is correct
7 Correct 14 ms 20104 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 1 ms 1612 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 13 ms 22172 KB Output is correct
12 Correct 783 ms 22164 KB Output is correct
13 Correct 1 ms 1612 KB Output is correct
14 Correct 800 ms 22168 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 760 ms 20100 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 768 ms 19808 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 392 ms 19640 KB Output is correct
21 Correct 387 ms 19660 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 967 ms 24572 KB Output is correct
24 Correct 5 ms 1612 KB Output is correct
25 Correct 975 ms 24804 KB Output is correct
26 Correct 855 ms 23876 KB Output is correct
27 Correct 756 ms 24652 KB Output is correct
28 Correct 860 ms 23700 KB Output is correct
29 Correct 779 ms 24720 KB Output is correct
30 Correct 1055 ms 24176 KB Output is correct
31 Correct 1014 ms 25520 KB Output is correct
32 Correct 1024 ms 24456 KB Output is correct
33 Correct 1034 ms 25520 KB Output is correct
34 Correct 1008 ms 25448 KB Output is correct
35 Correct 263 ms 13516 KB Output is correct
36 Correct 256 ms 13492 KB Output is correct
37 Correct 256 ms 13516 KB Output is correct
38 Correct 95 ms 7244 KB Output is correct
39 Correct 96 ms 7432 KB Output is correct
40 Correct 1583 ms 26384 KB Output is correct
41 Correct 97 ms 7300 KB Output is correct
42 Correct 1579 ms 26184 KB Output is correct
43 Correct 1544 ms 26348 KB Output is correct
44 Execution timed out 3059 ms 40312 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 15 ms 23096 KB Output is correct
4 Correct 13 ms 22116 KB Output is correct
5 Correct 14 ms 22176 KB Output is correct
6 Correct 12 ms 19808 KB Output is correct
7 Correct 14 ms 20104 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 1 ms 1612 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 13 ms 22172 KB Output is correct
12 Correct 783 ms 22164 KB Output is correct
13 Correct 1 ms 1612 KB Output is correct
14 Correct 800 ms 22168 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 760 ms 20100 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 768 ms 19808 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 392 ms 19640 KB Output is correct
21 Correct 387 ms 19660 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 967 ms 24572 KB Output is correct
24 Correct 5 ms 1612 KB Output is correct
25 Correct 975 ms 24804 KB Output is correct
26 Correct 855 ms 23876 KB Output is correct
27 Correct 756 ms 24652 KB Output is correct
28 Correct 860 ms 23700 KB Output is correct
29 Correct 779 ms 24720 KB Output is correct
30 Correct 1055 ms 24176 KB Output is correct
31 Correct 1014 ms 25520 KB Output is correct
32 Correct 1024 ms 24456 KB Output is correct
33 Correct 1034 ms 25520 KB Output is correct
34 Correct 1008 ms 25448 KB Output is correct
35 Correct 263 ms 13516 KB Output is correct
36 Correct 256 ms 13492 KB Output is correct
37 Correct 256 ms 13516 KB Output is correct
38 Correct 95 ms 7244 KB Output is correct
39 Correct 96 ms 7432 KB Output is correct
40 Correct 1583 ms 26384 KB Output is correct
41 Correct 97 ms 7300 KB Output is correct
42 Correct 1579 ms 26184 KB Output is correct
43 Correct 1544 ms 26348 KB Output is correct
44 Correct 1 ms 1612 KB Output is correct
45 Runtime error 4 ms 3020 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -