oj.uz

Submission #439546

# Submission time Handle Problem Language Result Execution time Memory
439546 2021-06-30T08:19:07 Z K4YAN Political Development (BOI17_politicaldevelopment) C++17
16 / 100
 1165 ms 38320 KB 
//Be Name Khoda
// 10:55 -> 10:50 shoroo
// 12:40 | 12:40
 
#include<bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
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, deg[mxn];
vector<int> dp[mxn][11];
vector<short int> kmk, g2[11];
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;
        deg[i] = 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});
                if(deg[i] < deg[v]) {
                    g2[2].push_back(i);
                }
                else {
                    g2[2].push_back(v);
                }
            }
        }
    }
 
}
 
void solve() {
 
    bool b;
    int tmp;
    for(int i = 3; i <= k; i++) {
        tmp = 0;
 
        for(int j = 0; j < n; j++) {
 
            for(w = 0; w < (int)(g[i - 1].size()); w++) {
                if(dp[j][i].size() >= 10) {
                    break;
                }
                
                if(edge[j][g2[i - 1][w]] == false) {
                    continue;
                }
                b = true;
                for(auto e : g[i - 1][w]) {
 
                    if(edge[j][e] == false) {
                        b = false;
                        break;
                    }
 
                }
 
                if(b == false) {
                    continue;
                }
                for(auto e : g[i - 1][w]) {
                    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);
                if(deg[g2[i - 1][w]] > deg[j]) {
                    g2[i].push_back(j);
                }
                else {
                    g2[i].push_back(g2[i - 1][w]);
                }
                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;
 
}

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 14 ms 23028 KB Output is correct
4 Correct 11 ms 22136 KB Output is correct
5 Correct 11 ms 22128 KB Output is correct
6 Correct 11 ms 19916 KB Output is correct
7 Correct 11 ms 20044 KB Output is correct
8 Correct 1 ms 1612 KB Output is correct
9 Correct 1 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 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 14 ms 23028 KB Output is correct
4 Correct 11 ms 22136 KB Output is correct
5 Correct 11 ms 22128 KB Output is correct
6 Correct 11 ms 19916 KB Output is correct
7 Correct 11 ms 20044 KB Output is correct
8 Correct 1 ms 1612 KB Output is correct
9 Correct 1 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 97 ms 22152 KB Output is correct
13 Correct 1 ms 1612 KB Output is correct
14 Correct 101 ms 22092 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 108 ms 20036 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 98 ms 19800 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 54 ms 19660 KB Output is correct
21 Correct 56 ms 19584 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 121 ms 24656 KB Output is correct
24 Correct 5 ms 1672 KB Output is correct
25 Correct 127 ms 24636 KB Output is correct
26 Correct 111 ms 23768 KB Output is correct
27 Correct 99 ms 24644 KB Output is correct
28 Correct 115 ms 23748 KB Output is correct
29 Correct 104 ms 24740 KB Output is correct
30 Correct 135 ms 24164 KB Output is correct
31 Correct 130 ms 25528 KB Output is correct
32 Correct 129 ms 24488 KB Output is correct
33 Correct 134 ms 25540 KB Output is correct
34 Correct 122 ms 25480 KB Output is correct
35 Correct 38 ms 13388 KB Output is correct
36 Correct 38 ms 13640 KB Output is correct
37 Correct 38 ms 13388 KB Output is correct
38 Correct 15 ms 7328 KB Output is correct
39 Correct 15 ms 7336 KB Output is correct
40 Correct 194 ms 26248 KB Output is correct
41 Correct 16 ms 7244 KB Output is correct
42 Correct 190 ms 26172 KB Output is correct
43 Correct 184 ms 26168 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 1 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 2 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 14 ms 23028 KB Output is correct
4 Correct 11 ms 22136 KB Output is correct
5 Correct 11 ms 22128 KB Output is correct
6 Correct 11 ms 19916 KB Output is correct
7 Correct 11 ms 20044 KB Output is correct
8 Correct 1 ms 1612 KB Output is correct
9 Correct 1 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 97 ms 22152 KB Output is correct
13 Correct 1 ms 1612 KB Output is correct
14 Correct 101 ms 22092 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 108 ms 20036 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 98 ms 19800 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 54 ms 19660 KB Output is correct
21 Correct 56 ms 19584 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 121 ms 24656 KB Output is correct
24 Correct 5 ms 1672 KB Output is correct
25 Correct 127 ms 24636 KB Output is correct
26 Correct 111 ms 23768 KB Output is correct
27 Correct 99 ms 24644 KB Output is correct
28 Correct 115 ms 23748 KB Output is correct
29 Correct 104 ms 24740 KB Output is correct
30 Correct 135 ms 24164 KB Output is correct
31 Correct 130 ms 25528 KB Output is correct
32 Correct 129 ms 24488 KB Output is correct
33 Correct 134 ms 25540 KB Output is correct
34 Correct 122 ms 25480 KB Output is correct
35 Correct 38 ms 13388 KB Output is correct
36 Correct 38 ms 13640 KB Output is correct
37 Correct 38 ms 13388 KB Output is correct
38 Correct 15 ms 7328 KB Output is correct
39 Correct 15 ms 7336 KB Output is correct
40 Correct 194 ms 26248 KB Output is correct
41 Correct 16 ms 7244 KB Output is correct
42 Correct 190 ms 26172 KB Output is correct
43 Correct 184 ms 26168 KB Output is correct
44 Correct 1165 ms 38320 KB Output is correct
45 Correct 2 ms 1612 KB Output is correct
46 Correct 189 ms 26032 KB Output is correct
47 Correct 371 ms 27696 KB Output is correct
48 Correct 185 ms 25856 KB Output is correct
49 Correct 386 ms 27704 KB Output is correct
50 Correct 372 ms 27516 KB Output is correct
51 Correct 798 ms 29608 KB Output is correct
52 Correct 12 ms 22220 KB Output is correct
53 Correct 938 ms 29728 KB Output is correct
54 Incorrect 867 ms 30068 KB Output isn't correct
55 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 14 ms 23028 KB Output is correct
4 Correct 11 ms 22136 KB Output is correct
5 Correct 11 ms 22128 KB Output is correct
6 Correct 11 ms 19916 KB Output is correct
7 Correct 11 ms 20044 KB Output is correct
8 Correct 1 ms 1612 KB Output is correct
9 Correct 1 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 97 ms 22152 KB Output is correct
13 Correct 1 ms 1612 KB Output is correct
14 Correct 101 ms 22092 KB Output is correct
15 Correct 1 ms 1612 KB Output is correct
16 Correct 108 ms 20036 KB Output is correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 98 ms 19800 KB Output is correct
19 Correct 2 ms 1612 KB Output is correct
20 Correct 54 ms 19660 KB Output is correct
21 Correct 56 ms 19584 KB Output is correct
22 Correct 5 ms 1612 KB Output is correct
23 Correct 121 ms 24656 KB Output is correct
24 Correct 5 ms 1672 KB Output is correct
25 Correct 127 ms 24636 KB Output is correct
26 Correct 111 ms 23768 KB Output is correct
27 Correct 99 ms 24644 KB Output is correct
28 Correct 115 ms 23748 KB Output is correct
29 Correct 104 ms 24740 KB Output is correct
30 Correct 135 ms 24164 KB Output is correct
31 Correct 130 ms 25528 KB Output is correct
32 Correct 129 ms 24488 KB Output is correct
33 Correct 134 ms 25540 KB Output is correct
34 Correct 122 ms 25480 KB Output is correct
35 Correct 38 ms 13388 KB Output is correct
36 Correct 38 ms 13640 KB Output is correct
37 Correct 38 ms 13388 KB Output is correct
38 Correct 15 ms 7328 KB Output is correct
39 Correct 15 ms 7336 KB Output is correct
40 Correct 194 ms 26248 KB Output is correct
41 Correct 16 ms 7244 KB Output is correct
42 Correct 190 ms 26172 KB Output is correct
43 Correct 184 ms 26168 KB Output is correct
44 Correct 1 ms 1612 KB Output is correct
45 Runtime error 4 ms 3096 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -