oj.uz

Submission #647965

# Submission time Handle Problem Language Result Execution time Memory
647965 2022-10-04T17:16:57 Z mychecksedad Political Development (BOI17_politicaldevelopment) C++17
16 / 100
 193 ms 341296 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 = 9900047;


int n, k;
vector<int> g[N], path;
vector<bool> vis(N);
vector<bitset<50001>> 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){
    if(a < 0) a += MO;
    return a >= MO ? a - MO : a;
}
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{
                dfs(u, vv);
            }
        }    
    }
    path.pop_back();
}

void solve(){
    cin >> n >> k;
    is.resize(n+1);
    int a = 0;
    for(int i = 0; i < n; ++i){
        int d; cin >> d; a += 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] * 3) % MO;

    for(int i = 0; i < n; ++i) if(!vis[i]) dfs(i, i);

    for(int j = 4; j <= k; ++j){
        bitset<50001> out, in;
        vector<vector<int>> t;
        bitset<N*10> m;

        for(auto &u: v){
            ll h = 0;
            for(int x: u) in[x] = 1, h += e[x];
            h = mod(h%MO);
            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:156:16: warning: unused variable 'aa' [-Wunused-variable]
  156 |     int T = 1, aa;
      |                ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25172 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 28 ms 55928 KB Output is correct
4 Correct 31 ms 55912 KB Output is correct
5 Correct 31 ms 55916 KB Output is correct
6 Correct 27 ms 55892 KB Output is correct
7 Correct 26 ms 55940 KB Output is correct
8 Correct 29 ms 55684 KB Output is correct
9 Correct 15 ms 25248 KB Output is correct
10 Correct 29 ms 55756 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25172 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 28 ms 55928 KB Output is correct
4 Correct 31 ms 55912 KB Output is correct
5 Correct 31 ms 55916 KB Output is correct
6 Correct 27 ms 55892 KB Output is correct
7 Correct 26 ms 55940 KB Output is correct
8 Correct 29 ms 55684 KB Output is correct
9 Correct 15 ms 25248 KB Output is correct
10 Correct 29 ms 55756 KB Output is correct
11 Correct 28 ms 55884 KB Output is correct
12 Correct 26 ms 55892 KB Output is correct
13 Correct 13 ms 25172 KB Output is correct
14 Correct 29 ms 55896 KB Output is correct
15 Correct 13 ms 25172 KB Output is correct
16 Correct 27 ms 55980 KB Output is correct
17 Correct 13 ms 25084 KB Output is correct
18 Correct 26 ms 55892 KB Output is correct
19 Correct 28 ms 55764 KB Output is correct
20 Correct 33 ms 55844 KB Output is correct
21 Correct 29 ms 55888 KB Output is correct
22 Correct 28 ms 55692 KB Output is correct
23 Correct 31 ms 55904 KB Output is correct
24 Correct 25 ms 55688 KB Output is correct
25 Correct 27 ms 55988 KB Output is correct
26 Correct 30 ms 56016 KB Output is correct
27 Correct 29 ms 56212 KB Output is correct
28 Correct 27 ms 56016 KB Output is correct
29 Correct 27 ms 56228 KB Output is correct
30 Correct 32 ms 55892 KB Output is correct
31 Correct 30 ms 56064 KB Output is correct
32 Correct 29 ms 55912 KB Output is correct
33 Correct 29 ms 56040 KB Output is correct
34 Correct 29 ms 56132 KB Output is correct
35 Correct 21 ms 40668 KB Output is correct
36 Correct 20 ms 40572 KB Output is correct
37 Correct 20 ms 40660 KB Output is correct
38 Correct 17 ms 32736 KB Output is correct
39 Correct 18 ms 32852 KB Output is correct
40 Correct 31 ms 55916 KB Output is correct
41 Correct 21 ms 32724 KB Output is correct
42 Correct 31 ms 55868 KB Output is correct
43 Correct 29 ms 55880 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 63528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25172 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 28 ms 55928 KB Output is correct
4 Correct 31 ms 55912 KB Output is correct
5 Correct 31 ms 55916 KB Output is correct
6 Correct 27 ms 55892 KB Output is correct
7 Correct 26 ms 55940 KB Output is correct
8 Correct 29 ms 55684 KB Output is correct
9 Correct 15 ms 25248 KB Output is correct
10 Correct 29 ms 55756 KB Output is correct
11 Correct 28 ms 55884 KB Output is correct
12 Correct 26 ms 55892 KB Output is correct
13 Correct 13 ms 25172 KB Output is correct
14 Correct 29 ms 55896 KB Output is correct
15 Correct 13 ms 25172 KB Output is correct
16 Correct 27 ms 55980 KB Output is correct
17 Correct 13 ms 25084 KB Output is correct
18 Correct 26 ms 55892 KB Output is correct
19 Correct 28 ms 55764 KB Output is correct
20 Correct 33 ms 55844 KB Output is correct
21 Correct 29 ms 55888 KB Output is correct
22 Correct 28 ms 55692 KB Output is correct
23 Correct 31 ms 55904 KB Output is correct
24 Correct 25 ms 55688 KB Output is correct
25 Correct 27 ms 55988 KB Output is correct
26 Correct 30 ms 56016 KB Output is correct
27 Correct 29 ms 56212 KB Output is correct
28 Correct 27 ms 56016 KB Output is correct
29 Correct 27 ms 56228 KB Output is correct
30 Correct 32 ms 55892 KB Output is correct
31 Correct 30 ms 56064 KB Output is correct
32 Correct 29 ms 55912 KB Output is correct
33 Correct 29 ms 56040 KB Output is correct
34 Correct 29 ms 56132 KB Output is correct
35 Correct 21 ms 40668 KB Output is correct
36 Correct 20 ms 40572 KB Output is correct
37 Correct 20 ms 40660 KB Output is correct
38 Correct 17 ms 32736 KB Output is correct
39 Correct 18 ms 32852 KB Output is correct
40 Correct 31 ms 55916 KB Output is correct
41 Correct 21 ms 32724 KB Output is correct
42 Correct 31 ms 55868 KB Output is correct
43 Correct 29 ms 55880 KB Output is correct
44 Incorrect 38 ms 63828 KB Output isn't correct
45 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25172 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 28 ms 55928 KB Output is correct
4 Correct 31 ms 55912 KB Output is correct
5 Correct 31 ms 55916 KB Output is correct
6 Correct 27 ms 55892 KB Output is correct
7 Correct 26 ms 55940 KB Output is correct
8 Correct 29 ms 55684 KB Output is correct
9 Correct 15 ms 25248 KB Output is correct
10 Correct 29 ms 55756 KB Output is correct
11 Correct 28 ms 55884 KB Output is correct
12 Correct 26 ms 55892 KB Output is correct
13 Correct 13 ms 25172 KB Output is correct
14 Correct 29 ms 55896 KB Output is correct
15 Correct 13 ms 25172 KB Output is correct
16 Correct 27 ms 55980 KB Output is correct
17 Correct 13 ms 25084 KB Output is correct
18 Correct 26 ms 55892 KB Output is correct
19 Correct 28 ms 55764 KB Output is correct
20 Correct 33 ms 55844 KB Output is correct
21 Correct 29 ms 55888 KB Output is correct
22 Correct 28 ms 55692 KB Output is correct
23 Correct 31 ms 55904 KB Output is correct
24 Correct 25 ms 55688 KB Output is correct
25 Correct 27 ms 55988 KB Output is correct
26 Correct 30 ms 56016 KB Output is correct
27 Correct 29 ms 56212 KB Output is correct
28 Correct 27 ms 56016 KB Output is correct
29 Correct 27 ms 56228 KB Output is correct
30 Correct 32 ms 55892 KB Output is correct
31 Correct 30 ms 56064 KB Output is correct
32 Correct 29 ms 55912 KB Output is correct
33 Correct 29 ms 56040 KB Output is correct
34 Correct 29 ms 56132 KB Output is correct
35 Correct 21 ms 40668 KB Output is correct
36 Correct 20 ms 40572 KB Output is correct
37 Correct 20 ms 40660 KB Output is correct
38 Correct 17 ms 32736 KB Output is correct
39 Correct 18 ms 32852 KB Output is correct
40 Correct 31 ms 55916 KB Output is correct
41 Correct 21 ms 32724 KB Output is correct
42 Correct 31 ms 55868 KB Output is correct
43 Correct 29 ms 55880 KB Output is correct
44 Correct 19 ms 33004 KB Output is correct
45 Incorrect 193 ms 341296 KB Output isn't correct
46 Halted 0 ms 0 KB -