oj.uz

Submission #873935

# Submission time Handle Problem Language Result Execution time Memory
873935 2023-11-16T03:31:39 Z Darren0724 Capital City (JOI20_capital_city) C++17
1 / 100
 450 ms 39180 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);
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 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]<<' '<<noc[c[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;
    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 8 ms 16120 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 5 ms 16080 KB Output is correct
10 Correct 5 ms 15960 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16120 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 5 ms 16080 KB Output is correct
10 Correct 5 ms 15960 KB Output is correct
11 Correct 6 ms 16104 KB Output is correct
12 Correct 6 ms 16220 KB Output is correct
13 Correct 7 ms 16220 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 6 ms 16076 KB Output is correct
16 Correct 7 ms 16216 KB Output is correct
17 Incorrect 9 ms 16232 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 38636 KB Output is correct
2 Correct 239 ms 39180 KB Output is correct
3 Correct 440 ms 38412 KB Output is correct
4 Correct 238 ms 39092 KB Output is correct
5 Incorrect 363 ms 36052 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16120 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 5 ms 16080 KB Output is correct
10 Correct 5 ms 15960 KB Output is correct
11 Correct 6 ms 16104 KB Output is correct
12 Correct 6 ms 16220 KB Output is correct
13 Correct 7 ms 16220 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 6 ms 16076 KB Output is correct
16 Correct 7 ms 16216 KB Output is correct
17 Incorrect 9 ms 16232 KB Output isn't correct
18 Halted 0 ms 0 KB -