Submission #1257025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257025		noyancanturk	Capital City (JOI20_capital_city)	C++20	100 / 100	2180 ms	46928 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

vector<int>v[lim];
int a[lim];
int ans;

int ded[lim];
int tin[lim],tout[lim],tt=1;

int parent[lim];

void dfs(int node,int par){
  parent[node]=par;
  tin[node]=tt++;
  for(int j:v[node]){
    if(j==par)continue;
    dfs(j,node);
  }
  tout[node]=tt-1;
}

struct comp{
  bool operator()(int x,int y)const {
    return tin[x]<tin[y];
  }
};

int vis[lim];

int tot;

int sz[lim];

int sbs(int node,int par){
  sz[node]=1;
  for(int j:v[node]){
    if(j==par||vis[j])continue;
    sz[node]+=sbs(j,node);
  }
  return sz[node];
}

int findcen(int node,int par){
  for(int j:v[node]){
    if(j!=par&&!vis[j]&&2*sz[j]>=tot)return findcen(j,node);
  }
  return node;
}

int cnt[lim];
unordered_set<int>taken;
vector<int>guys[lim];

void calccnt(int node,int par,int tocnt){
  cnt[a[node]]+=tocnt;
  for(int j:v[node]){
    if(j==par||vis[j])continue;
    calccnt(j,node,tocnt);
  }
}

void decomp(int node){
  // cerr<<node<<'\n';
  // cerr<<"huh\n";
  tot=sbs(node,0);
  node=findcen(node,0);
  // cerr<<node<<'\n';
  // cerr<<"norway\n";
  int did=0;
  if(!ded[a[node]]){
    calccnt(node,0,1);
    did=1;
  }
  if(cnt[a[node]]==guys[a[node]].size()){
    ded[a[node]]=1;
    taken.clear();
    set<int,comp>st;
    queue<int>need;
    unordered_set<int>cols;
    cols.insert(a[node]);
    for(int j:guys[a[node]]){
      need.push(j);
    }
    int head=need.front();
    need.pop();
    taken.insert(head);
    // cerr<<"head is "<<head<<'\n';
    // cerr<<"can get ";
    for(int j:v[head]){
      if(j!=parent[head]&&!vis[j]&&!taken.count(j)){
        // cerr<<j<<' ';
        st.insert(j);
      }
    }
    // cerr<<'\n';
    int cant=0;
    while(need.size()&&!cant){
      cerr<<need.size()<<'\n';
      int totake=need.front();
      need.pop();
      while(!taken.count(totake)&&!cant){
        if(!st.size()||tin[totake]<tin[*st.begin()]||tin[totake]>tout[*st.rbegin()]){
          if(!parent[head]||vis[parent[head]]){
            cant=1;
            break;
          }else{
            head=parent[head];
            if(cnt[a[head]]!=guys[a[head]].size()){
              cant=1;
              break;
            }
            if(!cols.count(a[head])){
              cols.insert(a[head]);
              for(int j:guys[a[head]]){
                need.push(j);
              }
            }
            // cerr<<"took old parent "<<head<<'\n';
            taken.insert(head);
            for(int j:v[head]){
              if(j!=parent[head]&&!vis[j]&&!taken.count(j)){
                st.insert(j);
              }
            }
          }
        }else{
          auto p=prev(st.upper_bound(totake));
          int guy=*p;
          if(cnt[a[guy]]!=guys[a[guy]].size()){
            cant=1;
            break;
          }
          if(!cols.count(a[guy])){
            cols.insert(a[guy]);
            for(int j:guys[a[guy]]){
              need.push(j);
            }
          }
          // cerr<<"took old fashion "<<guy<<'\n';
          taken.insert(guy);
          for(int j:v[guy]){
            if(j!=parent[guy]&&!vis[j]&&!taken.count(j)){
              st.insert(j);
            }
          }
        }
      }
      if(cols.size()>ans){
        cant=1;
        break;
      }
    }
    if(!cant){
      // cerr<<"found one\n";
      // cerr<<"cols :: ";
      // for(int i:cols)cerr<<i<<' ';
      // cerr<<'\n';
      // cerr<<"taken :: ";
      // for(int i:taken)cerr<<i<<' ';
      // cerr<<'\n';
      ans=min<int>(ans,cols.size()-1);
    }
  }else ded[a[node]]=1;
  if(did){
    calccnt(node,0,-1);
  }
  vis[node]=1;
  for(int j:v[node]){
    if(!vis[j]){
      decomp(j);
    }
  }
}

int main(){
  int n,__;
  cin>>n>>__;
  for(int i=0;i<n-1;i++){
    int x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x); 
  }
  for(int i=1;i<=n;i++){
    cin>>a[i];
    guys[a[i]].pb(i);
  }
  ans=n;
  dfs(1,0);
  cerr<<"here\n";
  decomp(1);
  cout<<ans<<'\n';
}

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