oj.uz

Submission #205098

# Submission time Handle Problem Language Result Execution time Memory
205098 2020-02-27T23:55:58 Z achibasadzishvili Mergers (JOI19_mergers) C++14
0 / 100
 165 ms 81264 KB 
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll P[500002][20],lvl[500002],pp[500002],in[500002],out[500002],timer,ch[500002];
ll n,k,bst[500002],c[500002],par[500002],p[500002],sz[500002],raod[500002];
ll fix[500002];
set<ll>st[500002];
vector<ll>v[500002],del[500002],fer[500002];
void dfs(ll x,ll par) {
    P[x][0]=par;
    pp[x] = par;
    for (int i=1;i<=19;i++)
        P[x][i]=P[P[x][i-1]][i-1];
    timer++;
    in[x]=timer;
    ch[x] = 1;
    for (int i=0;i<v[x].size();i++)
        if (v[x][i] != par) {
            lvl[v[x][i]]=lvl[x]+1;
            dfs(v[x][i],x);
            ch[x] += ch[v[x][i]];
        }
    out[x]=timer;
}

ll lca(ll a,ll b) {
    if(lvl[a] > lvl[b])swap(a,b);
    if (in[a] <= in[b] && out[b] <= out[a]) return a;
    for (int i=19;i>=0;i--)
        if (P[a][i])
            if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]]))
                a=P[a][i];
    return P[a][0];
}
ll find(ll x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}
void join(ll x,ll y){
    //cout << x << " " << y << endl;
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(sz[y] > sz[x])swap(x , y);
    sz[x] += sz[y];
    p[y] = x;
}
void solve(ll x){
    if(v[x].size() == 0){
        bst[x] = x;
        if(par[c[x]] != x)st[x].insert(c[x]);
        return;
    }
    for(int i=0; i<v[x].size(); i++)
        solve(v[x][i]);
    bst[x] = bst[v[x][0]];
    if(st[bst[x]].size() > 0){
        join(c[x] , (*st[bst[x]].begin()));
    }
    st[bst[x]].insert(c[x]);
    ll th = (*st[bst[x]].begin());
    for(int i=1; i<v[x].size(); i++){
        ll t = bst[v[x][i]];
        for(set<ll>::iterator it = st[t].begin(); it != st[t].end(); it++){
            join(th , (*it));
            st[bst[x]].insert((*it));
        }
    }
    for(int i=0; i<del[x].size(); i++)
        if(st[bst[x]].find(del[x][i]) != st[bst[x]].end())st[bst[x]].erase(st[bst[x]].find(del[x][i]));
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    
    for(int i=1; i<n; i++){
        ll x,y;
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    
    for(int i=1; i<=n; i++){
        cin >> c[i];
        fer[c[i]].pb(i);
    }
    
    dfs(1 , 0);
    
    for(int i=1; i<=k; i++){
        par[i] = fer[i][0];
        for(int j=1; j<fer[i].size(); j++)
            par[i] = lca(par[i] , fer[i][j]);
        del[par[i]].pb(i);
    }
    
    for(int i=1; i<=n; i++){
        sz[i] = 1;
        p[i] = i;
        v[i].clear();
    }
    
    for(int i=2; i<=n; i++)
        v[pp[i]].pb(i);
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<v[i].size(); j++)
            if(ch[v[i][j]] > ch[v[i][0]])
                swap(v[i][j] , v[i][0]);
    
    
    solve(1);
    
    for(int i=1; i<=n; i++){
        for(int j=0; j<v[i].size(); j++){
            ll x = v[i][j];
            if(find(c[i]) != find(c[x])){
                raod[c[i]]++;
                raod[c[x]]++;
            }
        }
    }
    ll ans = 1;
    for(int i=1; i<=k; i++){
        if(!fix[find(i)]){
            fix[find(i)] = 1;
            if(raod[find(i)] == 1)ans++;
        }
    }
    
    cout << ans / 2 << '\n';
    
    
    return 0;
}

Compilation message

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
mergers.cpp: In function 'void solve(int)':
mergers.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++)
                  ~^~~~~~~~~~~~
mergers.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<v[x].size(); i++){
                  ~^~~~~~~~~~~~
mergers.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<del[x].size(); i++)
                  ~^~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<fer[i].size(); j++)
                      ~^~~~~~~~~~~~~~
mergers.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<v[i].size(); j++)
                      ~^~~~~~~~~~~~
mergers.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[i].size(); j++){
                      ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59256 KB Output is correct
2 Correct 43 ms 59128 KB Output is correct
3 Correct 43 ms 59128 KB Output is correct
4 Correct 43 ms 59128 KB Output is correct
5 Correct 42 ms 59128 KB Output is correct
6 Correct 43 ms 59128 KB Output is correct
7 Correct 44 ms 59128 KB Output is correct
8 Correct 44 ms 59132 KB Output is correct
9 Correct 43 ms 59128 KB Output is correct
10 Correct 45 ms 59128 KB Output is correct
11 Correct 44 ms 59128 KB Output is correct
12 Correct 44 ms 59128 KB Output is correct
13 Incorrect 44 ms 59128 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59256 KB Output is correct
2 Correct 43 ms 59128 KB Output is correct
3 Correct 43 ms 59128 KB Output is correct
4 Correct 43 ms 59128 KB Output is correct
5 Correct 42 ms 59128 KB Output is correct
6 Correct 43 ms 59128 KB Output is correct
7 Correct 44 ms 59128 KB Output is correct
8 Correct 44 ms 59132 KB Output is correct
9 Correct 43 ms 59128 KB Output is correct
10 Correct 45 ms 59128 KB Output is correct
11 Correct 44 ms 59128 KB Output is correct
12 Correct 44 ms 59128 KB Output is correct
13 Incorrect 44 ms 59128 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59256 KB Output is correct
2 Correct 43 ms 59128 KB Output is correct
3 Correct 43 ms 59128 KB Output is correct
4 Correct 43 ms 59128 KB Output is correct
5 Correct 42 ms 59128 KB Output is correct
6 Correct 43 ms 59128 KB Output is correct
7 Correct 44 ms 59128 KB Output is correct
8 Correct 44 ms 59132 KB Output is correct
9 Correct 43 ms 59128 KB Output is correct
10 Correct 45 ms 59128 KB Output is correct
11 Correct 44 ms 59128 KB Output is correct
12 Correct 44 ms 59128 KB Output is correct
13 Incorrect 44 ms 59128 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 79192 KB Output is correct
2 Correct 165 ms 81264 KB Output is correct
3 Incorrect 47 ms 59768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59256 KB Output is correct
2 Correct 43 ms 59128 KB Output is correct
3 Correct 43 ms 59128 KB Output is correct
4 Correct 43 ms 59128 KB Output is correct
5 Correct 42 ms 59128 KB Output is correct
6 Correct 43 ms 59128 KB Output is correct
7 Correct 44 ms 59128 KB Output is correct
8 Correct 44 ms 59132 KB Output is correct
9 Correct 43 ms 59128 KB Output is correct
10 Correct 45 ms 59128 KB Output is correct
11 Correct 44 ms 59128 KB Output is correct
12 Correct 44 ms 59128 KB Output is correct
13 Incorrect 44 ms 59128 KB Output isn't correct
14 Halted 0 ms 0 KB -