Submission #944688

#	Time	Username	Problem	Language	Result	Execution time	Memory
944688		imarn	Capital City (JOI20_capital_city)	C++14	100 / 100	537 ms	39064 KiB

capital_city

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define double long double
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=2e5+5;
vector<int>g[N],co[N];
int sz[N],c[N],pr[N],up[N];
bool vis[N]{0},use[N]{0},usec[N]{0};
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
int getsize(int u,int p){
    sz[u]=1;for(auto v:g[u])if(v!=p&&!vis[v])sz[u]+=getsize(v,u);
    return sz[u];
}
int getct(int u,int p,int n){
    for(auto v:g[u])if(v!=p&&!vis[v]&&sz[v]*2>n)return getct(v,u,n);
    return u;
}
void dfs(int u,int p){
    up[u]=p;use[u]=1;for(auto v:g[u])if(v!=p&&!vis[v])dfs(v,u);
}
void rdfs(int u,int p){
    pr[u]=u;up[u]=u;use[u]=0;usec[c[u]]=0;
    for(auto v:g[u])if(v!=p&&!vis[v])rdfs(v,u);
}int ans=1e8;
void play(int u){
    u=getct(u,u,getsize(u,u));int cnt=1;
    vis[u]=1;dfs(u,u);bool ok=1;
    queue<int>q;q.push(c[u]);usec[c[u]]=1;
    while(!q.empty()){
        int cl=q.front();q.pop();
        for(int it : co[cl]){
            if(!use[it]){ok=0;break;}
            while(get(it)!=get(u)){
                int v=get(up[it]);pr[get(it)]=v;
                if(!usec[c[v]])q.push(c[v]),usec[c[v]]=1,cnt++;it=v;
            }
        }
    }if(ok)ans=min(cnt,ans);rdfs(u,u);
    for(auto v :g[u])if(!vis[v])play(v);

}
int main(){
    ios_base::sync_with_stdio(0);
    int n,k;cin>>n>>k;iota(pr,pr+n+1,0);
    for(int i=1,u,v;i<=n-1;i++){
        cin>>u>>v;g[u].pb(v);g[v].pb(u);
    }for(int i=1;i<=n;i++)cin>>c[i],co[c[i]].pb(i);
    play(1);cout<<ans-1;

}

Compilation message (stderr)

capital_city.cpp: In function 'void play(int)':
capital_city.cpp:46:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   46 |                 if(!usec[c[v]])q.push(c[v]),usec[c[v]]=1,cnt++;it=v;
      |                 ^~
capital_city.cpp:46:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   46 |                 if(!usec[c[v]])q.push(c[v]),usec[c[v]]=1,cnt++;it=v;
      |                                                                ^~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59