oj.uz

Submission #555324

# Submission time Handle Problem Language Result Execution time Memory
555324 2022-04-30T12:52:55 Z urosk Mergers (JOI19_mergers) C++14
48 / 100
 368 ms 262144 KB 
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 500005
ll n,k;
ll a[maxn];
ll dp[maxn][2];
ll b[maxn];
ll in[maxn];
ll out[maxn];
vector<ll> g[maxn];
vector<ll> v[maxn];
vector<ll> f[maxn];
ll ti = 1;
ll col = -1;
ll con[maxn];
ll dsu[maxn];
ll root(ll x){
    while(x!=dsu[x]){
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}
void upd(ll x,ll y){
    x = root(x); y = root(y);
    dsu[x] = y;
}
ll root2(ll x){
    while(x!=con[x]){
        con[x] = con[con[x]];
        x = con[x];
    }
    return x;
}
void upd2(ll x,ll y){
    x = root2(x); y = root2(y);
    con[x] = y;
}
void updg(ll x,ll y){
    upd2(x,y);
    f[x].pb(y);
    f[y].pb(x);
}
vector<vector<ll> > cnt;
void dfs(ll u,ll par){
    cnt[u][b[u]] = 1;
    for(ll s : g[u]){
        if(s==par) continue;
        dfs(s,u);
        for(ll i = 1;i<=k;i++) cnt[u][i]+=cnt[s][i];
    }
    bool flag =0;
    for(ll i = 1;i<=k;i++){
        if(cnt[u][i]!=sz(v[i])&&cnt[u][i]!=0) flag = 1;
    }
    if(flag) upd(u,par);
}
ll dis[maxn];
ll getnaj(ll u,ll par){
    ll y = u;
    for(ll s : f[u]){
        if(s==par) continue;
        dis[s] = dis[u] + 1;
        ll e = getnaj(s,u);
        if(dis[e]>dis[y]) y = e;
    }
    return y;
}
ll sizi = 0;
void brisi(ll u,ll par,ll x,vector<ll> w){
    w.pb(u);
    if(u==x){
        for(ll i = 0;i<sz(w)-1;i++){
            upd(w[i],w[i+1]);
        }
        sizi-=(sz(w)-1);
        return;
    }
    for(ll s : f[u]){
        if(s==par) continue;
        brisi(s,u,x,w);
    }
}
bool vis[maxn];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> k;
    iota(dsu+1,dsu+n+1,1);
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    cnt.resize(n+1);
    for(ll i = 0;i<=n;i++) cnt[i].resize(k+1);
    for(ll i = 1;i<=n;i++) cin >> b[i];
    for(ll i = 1;i<=n;i++){
        v[b[i]].pb(i);
    }
    dfs(1,1);
    for(ll i = 1;i<=n;i++){
        if(vis[root(i)]) continue;
        vis[root(i)] = 1;
        sizi++;
    }
    iota(con+1,con+n+1,1);
    for(ll i = 1;i<=n;i++){
        ll x = root(i);
        for(ll j : g[i]){
            ll y = root(j);
            if(root2(x)==root2(y)) continue;
            updg(x,y);
        }
    }
    //for(ll i= 1;i<=n;i++) cerr<<root(i)<< " ";
    //cerr<<endl;
    ll ans = 0;
    while(sizi>1){
        /*
        here;
        for(ll i = 1;i<=n;i++){
            if(sz(f[i])==0) continue;
            cerr<<"i: "<<i<<endl;
            for(ll x : f[i]) cerr<<x<< " ";
            cerr<<endl;
        }
        */
        ll poc = 1;
        for(ll i = 1;i<=n;i++) if(sz(f[i])>0) poc = i;
        //cerr<<"poc: "<<poc<<endl;
        fill(dis,dis+n+1,0);
        dis[0] = llinf;
        ll x = getnaj(poc,poc);
        //cerr<<x<<endl;

        fill(dis,dis+n+1,0);
        dis[0] = llinf;
        ll y = getnaj(x,x);
        brisi(x,x,y,{});
        //cerr<<y<<endl;
        for(ll i = 1;i<=n;i++) f[i].clear();
        iota(con+1,con+n+1,1);
        for(ll i = 1;i<=n;i++){
            ll x = root(i);
            for(ll j : g[i]){
                ll y = root(j);
                if(root2(x)==root2(y)) continue;
                updg(x,y);
            }
        }
        ans++;
    }
    cout<<ans<<endl;
	return 0;
}
/*
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 18 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 19 ms 35540 KB Output is correct
5 Correct 18 ms 35480 KB Output is correct
6 Correct 19 ms 35488 KB Output is correct
7 Correct 20 ms 35532 KB Output is correct
8 Correct 18 ms 35504 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 17 ms 35464 KB Output is correct
11 Correct 17 ms 35612 KB Output is correct
12 Correct 17 ms 35516 KB Output is correct
13 Correct 18 ms 35540 KB Output is correct
14 Correct 18 ms 35496 KB Output is correct
15 Correct 19 ms 35492 KB Output is correct
16 Correct 18 ms 35556 KB Output is correct
17 Correct 17 ms 35480 KB Output is correct
18 Correct 18 ms 35556 KB Output is correct
19 Correct 18 ms 35604 KB Output is correct
20 Correct 17 ms 35512 KB Output is correct
21 Correct 19 ms 35612 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 18 ms 35540 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 18 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 19 ms 35540 KB Output is correct
5 Correct 18 ms 35480 KB Output is correct
6 Correct 19 ms 35488 KB Output is correct
7 Correct 20 ms 35532 KB Output is correct
8 Correct 18 ms 35504 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 17 ms 35464 KB Output is correct
11 Correct 17 ms 35612 KB Output is correct
12 Correct 17 ms 35516 KB Output is correct
13 Correct 18 ms 35540 KB Output is correct
14 Correct 18 ms 35496 KB Output is correct
15 Correct 19 ms 35492 KB Output is correct
16 Correct 18 ms 35556 KB Output is correct
17 Correct 17 ms 35480 KB Output is correct
18 Correct 18 ms 35556 KB Output is correct
19 Correct 18 ms 35604 KB Output is correct
20 Correct 17 ms 35512 KB Output is correct
21 Correct 19 ms 35612 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 18 ms 35540 KB Output is correct
25 Correct 20 ms 35540 KB Output is correct
26 Correct 104 ms 83876 KB Output is correct
27 Correct 21 ms 37104 KB Output is correct
28 Correct 195 ms 112424 KB Output is correct
29 Correct 229 ms 111324 KB Output is correct
30 Correct 23 ms 40660 KB Output is correct
31 Correct 18 ms 35580 KB Output is correct
32 Correct 72 ms 109272 KB Output is correct
33 Correct 18 ms 35540 KB Output is correct
34 Correct 20 ms 37056 KB Output is correct
35 Correct 229 ms 111276 KB Output is correct
36 Correct 23 ms 37100 KB Output is correct
37 Correct 56 ms 71344 KB Output is correct
38 Correct 18 ms 35648 KB Output is correct
39 Correct 56 ms 71264 KB Output is correct
40 Correct 20 ms 35896 KB Output is correct
41 Correct 20 ms 36180 KB Output is correct
42 Correct 72 ms 71996 KB Output is correct
43 Correct 19 ms 36052 KB Output is correct
44 Correct 18 ms 35700 KB Output is correct
45 Correct 68 ms 104252 KB Output is correct
46 Correct 57 ms 70700 KB Output is correct
47 Correct 17 ms 35540 KB Output is correct
48 Correct 39 ms 50004 KB Output is correct
49 Correct 368 ms 129712 KB Output is correct
50 Correct 210 ms 125088 KB Output is correct
51 Correct 37 ms 50104 KB Output is correct
52 Correct 20 ms 37088 KB Output is correct
53 Correct 72 ms 72016 KB Output is correct
54 Correct 20 ms 37076 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 18 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 19 ms 35540 KB Output is correct
5 Correct 18 ms 35480 KB Output is correct
6 Correct 19 ms 35488 KB Output is correct
7 Correct 20 ms 35532 KB Output is correct
8 Correct 18 ms 35504 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 17 ms 35464 KB Output is correct
11 Correct 17 ms 35612 KB Output is correct
12 Correct 17 ms 35516 KB Output is correct
13 Correct 18 ms 35540 KB Output is correct
14 Correct 18 ms 35496 KB Output is correct
15 Correct 19 ms 35492 KB Output is correct
16 Correct 18 ms 35556 KB Output is correct
17 Correct 17 ms 35480 KB Output is correct
18 Correct 18 ms 35556 KB Output is correct
19 Correct 18 ms 35604 KB Output is correct
20 Correct 17 ms 35512 KB Output is correct
21 Correct 19 ms 35612 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 18 ms 35540 KB Output is correct
25 Correct 19 ms 35608 KB Output is correct
26 Correct 115 ms 87372 KB Output is correct
27 Correct 140 ms 87204 KB Output is correct
28 Correct 25 ms 37068 KB Output is correct
29 Correct 18 ms 35536 KB Output is correct
30 Correct 18 ms 35572 KB Output is correct
31 Correct 223 ms 87892 KB Output is correct
32 Correct 20 ms 37056 KB Output is correct
33 Correct 160 ms 92420 KB Output is correct
34 Correct 138 ms 88144 KB Output is correct
35 Correct 21 ms 37076 KB Output is correct
36 Correct 223 ms 88032 KB Output is correct
37 Correct 20 ms 35992 KB Output is correct
38 Correct 20 ms 36224 KB Output is correct
39 Correct 121 ms 87256 KB Output is correct
40 Correct 19 ms 36200 KB Output is correct
41 Correct 83 ms 49392 KB Output is correct
42 Correct 148 ms 89216 KB Output is correct
43 Correct 18 ms 35568 KB Output is correct
44 Correct 93 ms 54844 KB Output is correct
45 Correct 149 ms 90912 KB Output is correct
46 Correct 20 ms 37076 KB Output is correct
47 Correct 22 ms 37116 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 87344 KB Output is correct
2 Runtime error 116 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 18 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 19 ms 35540 KB Output is correct
5 Correct 18 ms 35480 KB Output is correct
6 Correct 19 ms 35488 KB Output is correct
7 Correct 20 ms 35532 KB Output is correct
8 Correct 18 ms 35504 KB Output is correct
9 Correct 18 ms 35516 KB Output is correct
10 Correct 17 ms 35464 KB Output is correct
11 Correct 17 ms 35612 KB Output is correct
12 Correct 17 ms 35516 KB Output is correct
13 Correct 18 ms 35540 KB Output is correct
14 Correct 18 ms 35496 KB Output is correct
15 Correct 19 ms 35492 KB Output is correct
16 Correct 18 ms 35556 KB Output is correct
17 Correct 17 ms 35480 KB Output is correct
18 Correct 18 ms 35556 KB Output is correct
19 Correct 18 ms 35604 KB Output is correct
20 Correct 17 ms 35512 KB Output is correct
21 Correct 19 ms 35612 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 18 ms 35540 KB Output is correct
25 Correct 20 ms 35540 KB Output is correct
26 Correct 104 ms 83876 KB Output is correct
27 Correct 21 ms 37104 KB Output is correct
28 Correct 195 ms 112424 KB Output is correct
29 Correct 229 ms 111324 KB Output is correct
30 Correct 23 ms 40660 KB Output is correct
31 Correct 18 ms 35580 KB Output is correct
32 Correct 72 ms 109272 KB Output is correct
33 Correct 18 ms 35540 KB Output is correct
34 Correct 20 ms 37056 KB Output is correct
35 Correct 229 ms 111276 KB Output is correct
36 Correct 23 ms 37100 KB Output is correct
37 Correct 56 ms 71344 KB Output is correct
38 Correct 18 ms 35648 KB Output is correct
39 Correct 56 ms 71264 KB Output is correct
40 Correct 20 ms 35896 KB Output is correct
41 Correct 20 ms 36180 KB Output is correct
42 Correct 72 ms 71996 KB Output is correct
43 Correct 19 ms 36052 KB Output is correct
44 Correct 18 ms 35700 KB Output is correct
45 Correct 68 ms 104252 KB Output is correct
46 Correct 57 ms 70700 KB Output is correct
47 Correct 17 ms 35540 KB Output is correct
48 Correct 39 ms 50004 KB Output is correct
49 Correct 368 ms 129712 KB Output is correct
50 Correct 210 ms 125088 KB Output is correct
51 Correct 37 ms 50104 KB Output is correct
52 Correct 20 ms 37088 KB Output is correct
53 Correct 72 ms 72016 KB Output is correct
54 Correct 20 ms 37076 KB Output is correct
55 Correct 19 ms 35608 KB Output is correct
56 Correct 115 ms 87372 KB Output is correct
57 Correct 140 ms 87204 KB Output is correct
58 Correct 25 ms 37068 KB Output is correct
59 Correct 18 ms 35536 KB Output is correct
60 Correct 18 ms 35572 KB Output is correct
61 Correct 223 ms 87892 KB Output is correct
62 Correct 20 ms 37056 KB Output is correct
63 Correct 160 ms 92420 KB Output is correct
64 Correct 138 ms 88144 KB Output is correct
65 Correct 21 ms 37076 KB Output is correct
66 Correct 223 ms 88032 KB Output is correct
67 Correct 20 ms 35992 KB Output is correct
68 Correct 20 ms 36224 KB Output is correct
69 Correct 121 ms 87256 KB Output is correct
70 Correct 19 ms 36200 KB Output is correct
71 Correct 83 ms 49392 KB Output is correct
72 Correct 148 ms 89216 KB Output is correct
73 Correct 18 ms 35568 KB Output is correct
74 Correct 93 ms 54844 KB Output is correct
75 Correct 149 ms 90912 KB Output is correct
76 Correct 20 ms 37076 KB Output is correct
77 Correct 22 ms 37116 KB Output is correct
78 Correct 114 ms 87344 KB Output is correct
79 Runtime error 116 ms 262144 KB Execution killed with signal 9
80 Halted 0 ms 0 KB -