oj.uz

Submission #873941

# Submission time Handle Problem Language Result Execution time Memory
873941 2023-11-16T04:57:00 Z Darren0724 Capital City (JOI20_capital_city) C++17
1 / 100
 511 ms 45020 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int N=200005;
int n,m;
int ans=INF;
vector<int> c(N),sz(N),adj[N],can(N),no(N),pa(N),vis(N),c1[N],inq(N),noc(N),cnt1(N),use(N),tmp;
void dfs(int k){
    sz[k]=1;
    for(int j:adj[k]){
        if(j==pa[k]||no[j])continue;
        pa[j]=k;
        dfs(j);
        sz[k]+=sz[j];
    }
}
int get_cen(int k,int goal){
    for(int j:adj[k]){
        if(j==pa[k]||no[j])continue;
        if(sz[j]>goal){
            return get_cen(j,goal);
        }
    }
    return k;
}
void dfs2(int k){
    tmp.push_back(c[k]);
    //cout<<"dfs2:"<<k<<' '<<c[k]<<endl;
    for(int j:adj[k]){
        if(j==pa[k]||no[j])continue;
        dfs2(j);
    }
}
void solve(int p){
    pa[p]=p;
    dfs(p);
    int cen=get_cen(p,sz[p]/2);
    pa[cen]=cen;
    dfs(cen);
    //cout<<"cen:"<<cen<<endl;
    queue<int> q;
    int flag=1,cnt=0;
    if(!noc[c[cen]]){
        vector<int> vis1,inq1;
        vis1.push_back(cen);
        vis[cen]=1;
        q.push(c[cen]);
        inq[c[cen]]=1;
        inq1.push_back(c[cen]);
        noc[c[cen]]=1;
        while(q.size()){
            int p=q.front();
            q.pop();
            //cout<<"p:"<<p<<endl;
            cnt++;
            for(int j:c1[p]){
                int t=j;
                while(!vis[t]){
                    //cout<<"t:"<<t<<' '<<c[t]<<' '<<pa[t]<<endl;
                    if(!noc[c[t]]){
                        noc[c[t]]=1;
                        inq[c[t]]=1;
                        inq1.push_back(c[t]);
                        q.push(c[t]);
                    }
                    else if(inq[c[t]]==0){
                        flag=0;
                    }
                    vis[t]=1;
                    vis1.push_back(t);
                    t=pa[t];
                }
            }
        }
        for(int j:vis1){
            vis[j]=0;
        }
        for(int j:inq1){
            inq[j]=0;
        }
        //cout<<"flag:"<<flag<<' '<<cnt<<endl;
        if(flag){
            ans=min(ans,cnt);
        }
    }
    noc[c[cen]]=1;
    no[cen]=1;
    vector<int> tmp1;
    for(int j:adj[cen]){
        if(!no[j]){
            tmp.clear();
            dfs2(j);
            for(int j:tmp){
                if(!use[j]){
                    use[j]++;
                    cnt1[j]++;
                    tmp1.push_back(j);
                }
            }
            for(int j:tmp){
                if(use[j]){
                    use[j]--;
                }
            }
        }
    }
    for(int j:tmp1){
        //cout<<j<<' '<<cnt1[j]<<endl;
        if(cnt1[j]>=2){
            //cout<<"get out "<<j<<endl;
            noc[j]=1;
        }
        cnt1[j]=0;
    }
    for(int j:adj[cen]){
        if(!no[j]){
            solve(j);
        }
    }
}
int32_t main() {
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
        c1[c[i]].push_back(i);
    }
    solve(1);
    cout<<ans-1<<endl;

    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 5 ms 17500 KB Output is correct
3 Correct 6 ms 17700 KB Output is correct
4 Correct 5 ms 17648 KB Output is correct
5 Correct 6 ms 17500 KB Output is correct
6 Correct 5 ms 17500 KB Output is correct
7 Correct 5 ms 17500 KB Output is correct
8 Correct 6 ms 17500 KB Output is correct
9 Correct 5 ms 17500 KB Output is correct
10 Correct 5 ms 17500 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 5 ms 17500 KB Output is correct
3 Correct 6 ms 17700 KB Output is correct
4 Correct 5 ms 17648 KB Output is correct
5 Correct 6 ms 17500 KB Output is correct
6 Correct 5 ms 17500 KB Output is correct
7 Correct 5 ms 17500 KB Output is correct
8 Correct 6 ms 17500 KB Output is correct
9 Correct 5 ms 17500 KB Output is correct
10 Correct 5 ms 17500 KB Output is correct
11 Correct 9 ms 17752 KB Output is correct
12 Correct 7 ms 17756 KB Output is correct
13 Correct 8 ms 17616 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 8 ms 17756 KB Output is correct
16 Correct 8 ms 17676 KB Output is correct
17 Incorrect 8 ms 17756 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 44356 KB Output is correct
2 Correct 286 ms 45020 KB Output is correct
3 Correct 511 ms 44100 KB Output is correct
4 Correct 304 ms 44812 KB Output is correct
5 Incorrect 442 ms 41744 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 5 ms 17500 KB Output is correct
3 Correct 6 ms 17700 KB Output is correct
4 Correct 5 ms 17648 KB Output is correct
5 Correct 6 ms 17500 KB Output is correct
6 Correct 5 ms 17500 KB Output is correct
7 Correct 5 ms 17500 KB Output is correct
8 Correct 6 ms 17500 KB Output is correct
9 Correct 5 ms 17500 KB Output is correct
10 Correct 5 ms 17500 KB Output is correct
11 Correct 9 ms 17752 KB Output is correct
12 Correct 7 ms 17756 KB Output is correct
13 Correct 8 ms 17616 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 8 ms 17756 KB Output is correct
16 Correct 8 ms 17676 KB Output is correct
17 Incorrect 8 ms 17756 KB Output isn't correct
18 Halted 0 ms 0 KB -