oj.uz

Submission #439531

# Submission time Handle Problem Language Result Execution time Memory
439531 2021-06-30T07:54:57 Z K4YAN Political Development (BOI17_politicaldevelopment) C++17
16 / 100
 3000 ms 40340 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 short int mxn = 5e3 + 1;
int n, k, q, w;
short int v;
vector<int> dp[mxn][11];
vector<short int> kmk;
vector<vector<short int>> g[11];
bool edge[mxn][mxn];

void input() {

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

}

void solve() {

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

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

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

                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(short 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 1628 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 17 ms 23048 KB Output is correct
4 Correct 13 ms 22092 KB Output is correct
5 Correct 15 ms 22092 KB Output is correct
6 Correct 13 ms 19792 KB Output is correct
7 Correct 14 ms 20044 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 2 ms 1484 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 1628 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 17 ms 23048 KB Output is correct
4 Correct 13 ms 22092 KB Output is correct
5 Correct 15 ms 22092 KB Output is correct
6 Correct 13 ms 19792 KB Output is correct
7 Correct 14 ms 20044 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 2 ms 1484 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 13 ms 22092 KB Output is correct
12 Correct 738 ms 22172 KB Output is correct
13 Correct 2 ms 1612 KB Output is correct
14 Correct 809 ms 22168 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 855 ms 20008 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 737 ms 19884 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 383 ms 19724 KB Output is correct
21 Correct 409 ms 19568 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 951 ms 24616 KB Output is correct
24 Correct 6 ms 1612 KB Output is correct
25 Correct 881 ms 24608 KB Output is correct
26 Correct 817 ms 23748 KB Output is correct
27 Correct 697 ms 24568 KB Output is correct
28 Correct 787 ms 23696 KB Output is correct
29 Correct 699 ms 24720 KB Output is correct
30 Correct 936 ms 24144 KB Output is correct
31 Correct 925 ms 25504 KB Output is correct
32 Correct 932 ms 24468 KB Output is correct
33 Correct 1041 ms 25484 KB Output is correct
34 Correct 917 ms 25460 KB Output is correct
35 Correct 236 ms 13388 KB Output is correct
36 Correct 239 ms 13552 KB Output is correct
37 Correct 230 ms 13388 KB Output is correct
38 Correct 84 ms 7304 KB Output is correct
39 Correct 83 ms 7324 KB Output is correct
40 Correct 1411 ms 26320 KB Output is correct
41 Correct 89 ms 7372 KB Output is correct
42 Correct 1436 ms 26144 KB Output is correct
43 Correct 1394 ms 26140 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 2 ms 1612 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 2 ms 1612 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 2 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 2988 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 1628 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 17 ms 23048 KB Output is correct
4 Correct 13 ms 22092 KB Output is correct
5 Correct 15 ms 22092 KB Output is correct
6 Correct 13 ms 19792 KB Output is correct
7 Correct 14 ms 20044 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 2 ms 1484 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 13 ms 22092 KB Output is correct
12 Correct 738 ms 22172 KB Output is correct
13 Correct 2 ms 1612 KB Output is correct
14 Correct 809 ms 22168 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 855 ms 20008 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 737 ms 19884 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 383 ms 19724 KB Output is correct
21 Correct 409 ms 19568 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 951 ms 24616 KB Output is correct
24 Correct 6 ms 1612 KB Output is correct
25 Correct 881 ms 24608 KB Output is correct
26 Correct 817 ms 23748 KB Output is correct
27 Correct 697 ms 24568 KB Output is correct
28 Correct 787 ms 23696 KB Output is correct
29 Correct 699 ms 24720 KB Output is correct
30 Correct 936 ms 24144 KB Output is correct
31 Correct 925 ms 25504 KB Output is correct
32 Correct 932 ms 24468 KB Output is correct
33 Correct 1041 ms 25484 KB Output is correct
34 Correct 917 ms 25460 KB Output is correct
35 Correct 236 ms 13388 KB Output is correct
36 Correct 239 ms 13552 KB Output is correct
37 Correct 230 ms 13388 KB Output is correct
38 Correct 84 ms 7304 KB Output is correct
39 Correct 83 ms 7324 KB Output is correct
40 Correct 1411 ms 26320 KB Output is correct
41 Correct 89 ms 7372 KB Output is correct
42 Correct 1436 ms 26144 KB Output is correct
43 Correct 1394 ms 26140 KB Output is correct
44 Execution timed out 3096 ms 40340 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 1628 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 17 ms 23048 KB Output is correct
4 Correct 13 ms 22092 KB Output is correct
5 Correct 15 ms 22092 KB Output is correct
6 Correct 13 ms 19792 KB Output is correct
7 Correct 14 ms 20044 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 2 ms 1484 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 13 ms 22092 KB Output is correct
12 Correct 738 ms 22172 KB Output is correct
13 Correct 2 ms 1612 KB Output is correct
14 Correct 809 ms 22168 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 855 ms 20008 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 737 ms 19884 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 383 ms 19724 KB Output is correct
21 Correct 409 ms 19568 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 951 ms 24616 KB Output is correct
24 Correct 6 ms 1612 KB Output is correct
25 Correct 881 ms 24608 KB Output is correct
26 Correct 817 ms 23748 KB Output is correct
27 Correct 697 ms 24568 KB Output is correct
28 Correct 787 ms 23696 KB Output is correct
29 Correct 699 ms 24720 KB Output is correct
30 Correct 936 ms 24144 KB Output is correct
31 Correct 925 ms 25504 KB Output is correct
32 Correct 932 ms 24468 KB Output is correct
33 Correct 1041 ms 25484 KB Output is correct
34 Correct 917 ms 25460 KB Output is correct
35 Correct 236 ms 13388 KB Output is correct
36 Correct 239 ms 13552 KB Output is correct
37 Correct 230 ms 13388 KB Output is correct
38 Correct 84 ms 7304 KB Output is correct
39 Correct 83 ms 7324 KB Output is correct
40 Correct 1411 ms 26320 KB Output is correct
41 Correct 89 ms 7372 KB Output is correct
42 Correct 1436 ms 26144 KB Output is correct
43 Correct 1394 ms 26140 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 -