제출 #205100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205100		achibasadzishvili	Mergers (JOI19_mergers)	C++17	100 / 100	1982 ms	232040 KiB

mergers

#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]);
    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(c[x] , (*it));
            st[bst[x]].insert((*it));
        }
    }
    for(int i=0; i<del[x].size(); i++)
        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 j=0; j<fer[i].size(); j++){
            ll x = fer[i][j];
            while(1){
                join(i , c[x]);
                if(x == par[i])break;
                x = pp[x];
            }
        }*/
    }
    
    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[find(c[i])]++;
                raod[find(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;
}

컴파일 시 표준 에러 (stderr) 메시지

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:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<v[x].size(); i++){
                  ~^~~~~~~~~~~~
mergers.cpp:71: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:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<fer[i].size(); j++)
                      ~^~~~~~~~~~~~~~
mergers.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<v[i].size(); j++)
                      ~^~~~~~~~~~~~
mergers.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[i].size(); j++){
                      ~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30