제출 #1272223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272223		trandangquang	수도 (JOI20_capital_city)	C++20	100 / 100	540 ms	113964 KiB

capital_city

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

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define bit(s,i) (((s)>>(i))&1)
#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define ii pair<int,int>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ll long long
#define __builtin_popcount(a) __builtin_popcountll(a)

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=2e5+5;;
const int N2=1e6+5;

int n,k,c[N];
vector<int> adj[N],lst[N];

void input(){
    cin>>n>>k;
    rep(i,n-1){
        int u,v; cin>>u>>v;
        adj[u].eb(v); adj[v].eb(u);
    }
    foru(i,1,n) cin>>c[i], lst[c[i]].eb(i);
}

int sz[N],up[N][20],h[N];
void pre(int u, int p=-1){
    sz[u]=1;
    for(int v:adj[u]) if(v!=p){
        up[v][0]=u;
        foru(i,1,17) up[v][i]=up[up[v][i-1]][i-1];
        h[v]=h[u]+1;
        pre(v,u);
        sz[u]+=sz[v];
    }
}

int lca(int u, int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    foru(i,0,17) if(bit(d,i)) u=up[u][i];
    if(u==v) return u;
    ford(i,17,0) if(up[u][i]!=up[v][i]) u=up[u][i], v=up[v][i];
    return up[u][0];
}

int head[N],idCh[N],curCh;
int tin[N],tout[N],tour[N],tim;
void hld(int u, int p=-1){
    if(!head[curCh]){
        head[curCh]=u;
    }
    idCh[u]=curCh;
    tin[u]=++tim;
    tour[tim]=u;

    int bigC=-1;
    for(int v:adj[u]) if(v!=p){
        if(bigC==-1 || sz[bigC]<sz[v]) bigC=v;
    }

    if(bigC!=-1) hld(bigC,u);
    for(int v:adj[u]) if(v!=p && v!=bigC){
        ++curCh;
        hld(v,u);
    }

    tout[u]=tim;
}

vector<int> nw[N2];
int st[N2],cur;
void build(int id, int l, int r){
    st[id]=++cur;
    foru(i,l,r){
        nw[st[id]].eb(c[tour[i]]);
    }
    if(l==r) return;
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}

void buildTree(){
    cur=k;
    build(1,1,n);
}

void updTree(int u, int v, int val, int id=1, int l=1, int r=n){
    if(u>r||v<l) return;
    if(u<=l && r<=v){
        nw[val].eb(st[id]);
        return;
    }
    int mid=(l+r)>>1;
    updTree(u,v,val,id<<1,l,mid);
    updTree(u,v,val,id<<1|1,mid+1,r);
}
void add(int x, int y, int p){
    while(idCh[x]!=idCh[y]){
        updTree(tin[head[idCh[x]]],tin[x],p);
        x=up[head[idCh[x]]][0];
    }
    updTree(tin[y],tin[x],p);
}
void upd(int x, int y, int p){
    int l=lca(x,y);
    add(x,l,p);
    add(y,l,p);
}
void buildEdge(){
    foru(i,1,k){
        sort(all(lst[i]), [](int x, int y){return tin[x]<tin[y];});
        foru(j,0,sz(lst[i])-2){
            upd(lst[i][j], lst[i][j+1], i);
        }
    }
}

int low[N2],num[N2],idcc[N2],numcc,szK[N2];
int stk[N2],top; bool del[N2];

void dfs(int u){
    low[u]=num[u]=++tim;
    stk[++top]=u;

    for(int v:nw[u]){
        if(del[v]) continue;
        if(!num[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        } else{
            low[u]=min(low[u],num[v]);
        }
    }

    if(low[u]==num[u]){
        ++numcc;
        int v;
        do {
            v=stk[top]; --top;
            del[v]=true;
            idcc[v]=numcc;
            if(v<=k) ++szK[numcc];
        }
        while(v!=u);
    }
}

int out[N2];
void compressGraph(){
    tim=0;
    foru(i,1,cur) if(!num[i]) dfs(i);
    foru(u,1,cur){
        for(int v:nw[u]){
            if(idcc[u]!=idcc[v]){
                out[idcc[u]]++;
            }
        }
    }
}

void answer(){
    int res=1e9;
    foru(i,1,numcc){
        if(!out[i]) mini(res,szK[i]);
    }
    cout<<res-1<<'\n';
}

void solve(){
    input();
    pre(1); hld(1);
    buildTree();
    buildEdge();
    compressGraph();
    answer();
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    solve();
}

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

capital_city.cpp: In function 'int32_t main()':
capital_city.cpp:193:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:194:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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