oj.uz

Submission #647981

# Submission time Handle Problem Language Result Execution time Memory
647981 2022-10-04T17:33:43 Z mychecksedad Political Development (BOI17_politicaldevelopment) C++17
77 / 100
 3000 ms 366340 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20, MO = 99000007;


int n, k;
vector<int> g[N], path;
vector<bool> vis(N);
vector<bitset<50005>> is;
ll e[N];
void dfs(int v, int p){
    vis[v] = 1;
    path.pb(v);
    for(int u: g[v]){
        if(u != p){
            if(vis[u]){
                if(path[path.size() - 3] == u){
                    cout << 3;
                    exit(0);
                }
            }else{
                dfs(u, v);
            }
        }    
    }
    path.pop_back();
}

int mod(ll a){
    return ((a%MO)+MO)%MO;
}
vector<vector<int>> v;
void dfs2(int vv, int p){
    vis[vv] = 1;
    path.pb(vv);
    for(int u: g[vv]){
        if(u != p){
            if(vis[u]){
                if(path[path.size() - 3] == u){
                    v.pb({vv, path[path.size() - 2], path[path.size() - 3]});
                }
            }else{
                dfs2(u, vv);
            }
        }    
    }
    path.pop_back();
}

void solve(){
    cin >> n >> k;
    is.resize(n+1);
    for(int i = 0; i < n; ++i){
        int d; cin >> d; 
        for(int j = 0; j < d; ++j){
            int x; cin >> x; g[i].pb(x); is[i][x] = 1;
        }
    }
    if(k <= 2){
        for(int i = 0; i < n; ++i){
            if(g[i].size()){
                cout << 2;
                return;
            }
        }
        cout << 1;
        return;
    }
    if(k <= 3){
        for(int i = 0; i < n; ++i) if(!vis[i]) dfs(i, i);
        for(int i = 0; i < n; ++i){
            if(g[i].size()){
                cout << 2;
                return;
            }
        }
        cout << 1;
        return;
    }

    e[0] = 1;
    for(int i = 1; i < N; ++i) e[i] = (e[i - 1] * 5) % MO;

    bool o = 0;
    for(int i = 0; i < n; ++i) if(g[i].size() > 0) o = 1;
    if(!o){
        cout << 1;
        return;
    }
    for(int i = 0; i < n; ++i) for(int u: g[i]) if(u < i) v.pb(vector<int> {u, i});
    for(int j = 3; j <= k; ++j){
        bitset<50005> out, in;
        vector<vector<int>> t;
        bitset<N*100> m;

        for(auto &u: v){
            ll h = 0;
            for(int x: u) in[x] = 1, h += e[x];
            h = mod(h);
            vector<int> extend;
            for(int x: u){
                for(int e: g[x]){
                    if(!out[e] && !in[e]){
                        out[e] = 1;
                        extend.pb(e);
                    }
                }
            }
            for(int x: extend){
                out[x] = 0;
                bool ok = 1;
                for(int p: u){
                    if(!is[p][x]){
                        ok = 0;
                        break;
                    }
                }
                if(ok){
                    h = mod(h + e[x]);
                    if(!m[h]){
                        m[h] = 1;
                        u.pb(x);
                        t.pb(u);
                        u.pop_back();
                    }
                    h = mod(h - e[x]);
                }
            }
            for(int x: u) in[x] = 0;
        }
        if(t.size() == 0){
            cout << j - 1;
            return;
        }
        v = t;
    }
    cout << k;
}   





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:159:16: warning: unused variable 'aa' [-Wunused-variable]
  159 |     int T = 1, aa;
      |                ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36180 KB Output is correct
2 Correct 21 ms 36184 KB Output is correct
3 Correct 36 ms 66868 KB Output is correct
4 Correct 33 ms 66936 KB Output is correct
5 Correct 35 ms 66952 KB Output is correct
6 Correct 34 ms 66924 KB Output is correct
7 Correct 33 ms 66900 KB Output is correct
8 Correct 32 ms 66780 KB Output is correct
9 Correct 19 ms 36192 KB Output is correct
10 Correct 30 ms 66788 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36180 KB Output is correct
2 Correct 21 ms 36184 KB Output is correct
3 Correct 36 ms 66868 KB Output is correct
4 Correct 33 ms 66936 KB Output is correct
5 Correct 35 ms 66952 KB Output is correct
6 Correct 34 ms 66924 KB Output is correct
7 Correct 33 ms 66900 KB Output is correct
8 Correct 32 ms 66780 KB Output is correct
9 Correct 19 ms 36192 KB Output is correct
10 Correct 30 ms 66788 KB Output is correct
11 Correct 32 ms 66924 KB Output is correct
12 Correct 33 ms 66848 KB Output is correct
13 Correct 20 ms 36204 KB Output is correct
14 Correct 34 ms 66928 KB Output is correct
15 Correct 20 ms 36196 KB Output is correct
16 Correct 31 ms 66912 KB Output is correct
17 Correct 19 ms 36144 KB Output is correct
18 Correct 33 ms 66896 KB Output is correct
19 Correct 31 ms 66752 KB Output is correct
20 Correct 37 ms 66820 KB Output is correct
21 Correct 32 ms 66928 KB Output is correct
22 Correct 30 ms 66688 KB Output is correct
23 Correct 31 ms 66892 KB Output is correct
24 Correct 32 ms 66780 KB Output is correct
25 Correct 35 ms 66880 KB Output is correct
26 Correct 34 ms 67076 KB Output is correct
27 Correct 38 ms 67276 KB Output is correct
28 Correct 32 ms 67024 KB Output is correct
29 Correct 31 ms 67320 KB Output is correct
30 Correct 32 ms 66856 KB Output is correct
31 Correct 33 ms 67040 KB Output is correct
32 Correct 34 ms 66900 KB Output is correct
33 Correct 39 ms 67120 KB Output is correct
34 Correct 33 ms 67136 KB Output is correct
35 Correct 27 ms 51604 KB Output is correct
36 Correct 26 ms 51668 KB Output is correct
37 Correct 26 ms 51652 KB Output is correct
38 Correct 22 ms 43744 KB Output is correct
39 Correct 21 ms 43860 KB Output is correct
40 Correct 36 ms 66964 KB Output is correct
41 Correct 23 ms 43860 KB Output is correct
42 Correct 34 ms 66860 KB Output is correct
43 Correct 36 ms 66856 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 74580 KB Output is correct
2 Correct 27 ms 44140 KB Output is correct
3 Correct 28 ms 44036 KB Output is correct
4 Correct 29 ms 43988 KB Output is correct
5 Correct 32 ms 44020 KB Output is correct
6 Correct 30 ms 44032 KB Output is correct
7 Correct 32 ms 44108 KB Output is correct
8 Correct 30 ms 44112 KB Output is correct
9 Correct 30 ms 44116 KB Output is correct
10 Correct 28 ms 44116 KB Output is correct
11 Correct 410 ms 366320 KB Output is correct
12 Correct 34 ms 44108 KB Output is correct
13 Correct 422 ms 366340 KB Output is correct
14 Correct 30 ms 44116 KB Output is correct
15 Correct 499 ms 366316 KB Output is correct
16 Correct 416 ms 366328 KB Output is correct
17 Correct 440 ms 366324 KB Output is correct
18 Correct 430 ms 366228 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36180 KB Output is correct
2 Correct 21 ms 36184 KB Output is correct
3 Correct 36 ms 66868 KB Output is correct
4 Correct 33 ms 66936 KB Output is correct
5 Correct 35 ms 66952 KB Output is correct
6 Correct 34 ms 66924 KB Output is correct
7 Correct 33 ms 66900 KB Output is correct
8 Correct 32 ms 66780 KB Output is correct
9 Correct 19 ms 36192 KB Output is correct
10 Correct 30 ms 66788 KB Output is correct
11 Correct 32 ms 66924 KB Output is correct
12 Correct 33 ms 66848 KB Output is correct
13 Correct 20 ms 36204 KB Output is correct
14 Correct 34 ms 66928 KB Output is correct
15 Correct 20 ms 36196 KB Output is correct
16 Correct 31 ms 66912 KB Output is correct
17 Correct 19 ms 36144 KB Output is correct
18 Correct 33 ms 66896 KB Output is correct
19 Correct 31 ms 66752 KB Output is correct
20 Correct 37 ms 66820 KB Output is correct
21 Correct 32 ms 66928 KB Output is correct
22 Correct 30 ms 66688 KB Output is correct
23 Correct 31 ms 66892 KB Output is correct
24 Correct 32 ms 66780 KB Output is correct
25 Correct 35 ms 66880 KB Output is correct
26 Correct 34 ms 67076 KB Output is correct
27 Correct 38 ms 67276 KB Output is correct
28 Correct 32 ms 67024 KB Output is correct
29 Correct 31 ms 67320 KB Output is correct
30 Correct 32 ms 66856 KB Output is correct
31 Correct 33 ms 67040 KB Output is correct
32 Correct 34 ms 66900 KB Output is correct
33 Correct 39 ms 67120 KB Output is correct
34 Correct 33 ms 67136 KB Output is correct
35 Correct 27 ms 51604 KB Output is correct
36 Correct 26 ms 51668 KB Output is correct
37 Correct 26 ms 51652 KB Output is correct
38 Correct 22 ms 43744 KB Output is correct
39 Correct 21 ms 43860 KB Output is correct
40 Correct 36 ms 66964 KB Output is correct
41 Correct 23 ms 43860 KB Output is correct
42 Correct 34 ms 66860 KB Output is correct
43 Correct 36 ms 66856 KB Output is correct
44 Correct 251 ms 87084 KB Output is correct
45 Correct 30 ms 44044 KB Output is correct
46 Correct 52 ms 75432 KB Output is correct
47 Correct 59 ms 76144 KB Output is correct
48 Correct 48 ms 75408 KB Output is correct
49 Correct 62 ms 76192 KB Output is correct
50 Correct 58 ms 76080 KB Output is correct
51 Correct 101 ms 77652 KB Output is correct
52 Correct 35 ms 66912 KB Output is correct
53 Correct 1809 ms 77756 KB Output is correct
54 Correct 115 ms 77824 KB Output is correct
55 Correct 46 ms 75084 KB Output is correct
56 Correct 41 ms 66960 KB Output is correct
57 Correct 40 ms 74592 KB Output is correct
58 Correct 1807 ms 77700 KB Output is correct
59 Correct 54 ms 75984 KB Output is correct
60 Correct 47 ms 75084 KB Output is correct
61 Correct 58 ms 75964 KB Output is correct
62 Correct 61 ms 75916 KB Output is correct
63 Correct 242 ms 87080 KB Output is correct
64 Correct 170 ms 81544 KB Output is correct
65 Correct 55 ms 75372 KB Output is correct
66 Correct 58 ms 75912 KB Output is correct
67 Correct 149 ms 77692 KB Output is correct
68 Correct 142 ms 81548 KB Output is correct
69 Correct 49 ms 75328 KB Output is correct
70 Correct 71 ms 76176 KB Output is correct
71 Correct 145 ms 77796 KB Output is correct
72 Correct 101 ms 76840 KB Output is correct
73 Correct 40 ms 75012 KB Output is correct
74 Correct 65 ms 76124 KB Output is correct
75 Correct 102 ms 76796 KB Output is correct
76 Correct 90 ms 75504 KB Output is correct
77 Correct 68 ms 76544 KB Output is correct
78 Correct 49 ms 75028 KB Output is correct
79 Correct 41 ms 60284 KB Output is correct
80 Correct 97 ms 75460 KB Output is correct
81 Correct 71 ms 76548 KB Output is correct
82 Correct 38 ms 51796 KB Output is correct
83 Correct 54 ms 60260 KB Output is correct
84 Correct 67 ms 76272 KB Output is correct
85 Correct 30 ms 51796 KB Output is correct
86 Correct 64 ms 76284 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36180 KB Output is correct
2 Correct 21 ms 36184 KB Output is correct
3 Correct 36 ms 66868 KB Output is correct
4 Correct 33 ms 66936 KB Output is correct
5 Correct 35 ms 66952 KB Output is correct
6 Correct 34 ms 66924 KB Output is correct
7 Correct 33 ms 66900 KB Output is correct
8 Correct 32 ms 66780 KB Output is correct
9 Correct 19 ms 36192 KB Output is correct
10 Correct 30 ms 66788 KB Output is correct
11 Correct 32 ms 66924 KB Output is correct
12 Correct 33 ms 66848 KB Output is correct
13 Correct 20 ms 36204 KB Output is correct
14 Correct 34 ms 66928 KB Output is correct
15 Correct 20 ms 36196 KB Output is correct
16 Correct 31 ms 66912 KB Output is correct
17 Correct 19 ms 36144 KB Output is correct
18 Correct 33 ms 66896 KB Output is correct
19 Correct 31 ms 66752 KB Output is correct
20 Correct 37 ms 66820 KB Output is correct
21 Correct 32 ms 66928 KB Output is correct
22 Correct 30 ms 66688 KB Output is correct
23 Correct 31 ms 66892 KB Output is correct
24 Correct 32 ms 66780 KB Output is correct
25 Correct 35 ms 66880 KB Output is correct
26 Correct 34 ms 67076 KB Output is correct
27 Correct 38 ms 67276 KB Output is correct
28 Correct 32 ms 67024 KB Output is correct
29 Correct 31 ms 67320 KB Output is correct
30 Correct 32 ms 66856 KB Output is correct
31 Correct 33 ms 67040 KB Output is correct
32 Correct 34 ms 66900 KB Output is correct
33 Correct 39 ms 67120 KB Output is correct
34 Correct 33 ms 67136 KB Output is correct
35 Correct 27 ms 51604 KB Output is correct
36 Correct 26 ms 51668 KB Output is correct
37 Correct 26 ms 51652 KB Output is correct
38 Correct 22 ms 43744 KB Output is correct
39 Correct 21 ms 43860 KB Output is correct
40 Correct 36 ms 66964 KB Output is correct
41 Correct 23 ms 43860 KB Output is correct
42 Correct 34 ms 66860 KB Output is correct
43 Correct 36 ms 66856 KB Output is correct
44 Correct 28 ms 43996 KB Output is correct
45 Correct 328 ms 362656 KB Output is correct
46 Execution timed out 3076 ms 356860 KB Time limit exceeded
47 Halted 0 ms 0 KB -