oj.uz

답안 #676753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676753 2023-01-01T03:35:04 Z victor_gao 수도 (JOI20_capital_city) C++17
1 / 100
 1406 ms 524288 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,k;
struct SCC{
    vector<int>g[30*N];
    vector<pii>edge;
    int dfn[N],low[N],dft=0,boss[30*N],val[30*N],dp[30*N],nscc=0;
    bool ins[N],vis[N];
    stack<int>st;
    void add_edge(int i,int j){
        // i -> j
        g[i].push_back(j);
        edge.push_back({i,j});
    }
    void tarjan(int p){
        dfn[p]=low[p]=++dft;
        st.push(p); ins[p]=1;
        for (auto i:g[p]){
            if (!dfn[i]){
                tarjan(i);
                low[p]=min(low[p],low[i]);
            }
            else if (ins[i]&&dfn[i]<dfn[p])
                low[p]=min(low[p],dfn[i]);
        }
        if (low[p]==dfn[p]){
            nscc++;
        //    cout<<"find cycle "<<nscc<<" : ";
            for (int x=0;x!=p;st.pop()){
                x=st.top(); ins[x]=0;
                boss[x]=nscc;
                if (x<=k) val[nscc]++;
    //            cout<<x<<" ";
            }
     //       cout<<"val "<<val[nscc]<<'\n';
        }
    }
    void build(){
        for (int i=0;i<=28*n;i++)
            g[i].clear();
        for (auto i:edge){
            if (boss[i.x]!=boss[i.y]){
    //            cout<<"edge "<<boss[i.x]<<' '<<boss[i.y]<<'\n';
                g[boss[i.x]].push_back(boss[i.y]);
            }
        }
    }
    int dfs(int p){
        if (vis[p]) return dp[p];
        vis[p]=1; dp[p]=val[p];
        for (auto i:g[p])
            dp[p]+=dfs(i);
        return dp[p];
    }
}scc;
int cap[N],vis[N],son[N],all_col[N],sub_col[N],fa[N],have[N];
vector<int>g[N],path,sub_path;
int get_centroid(int p,int lp,int sz){
    for (auto i:g[p]){
        if (!vis[i]&&i!=lp&&son[i]>sz/2)
            return get_centroid(i,p,sz);
    }
    return p;
}
int dfs1(int p,int lp){
    son[p]=1;
    path.push_back(p);
    for (auto i:g[p]){
        if (!vis[i]&&i!=lp)
            son[p]+=dfs1(i,p);
    }
    return son[p];
}
void dfs2(int p,int lp){
    fa[p]=lp;
    sub_path.push_back(p);
    for (auto i:g[p]){
        if (!vis[i]&&i!=lp)
            dfs2(i,p);
    }
}
void build(int root,int dep){
    for (auto i:sub_path){
        sub_col[cap[i]]++;
        scc.add_edge(dep*n+i,cap[i]);
  //      cout<<"add_1 "<<dep*n+i<<' '<<cap[i]<<'\n';
    }
    /*
    cout<<"sub_col ";
    for (int i=1;i<=k;i++)
        cout<<sub_col[i]<<' ';
    cout<<'\n';
    */
    for (auto i:sub_path){
        if (all_col[cap[i]]==sub_col[cap[i]])
            continue;
        int p=i;
      //  cout<<"try "<<i<<" "<<cap[i]<<'\n';
        while (!have[p]){
            scc.add_edge(cap[i],dep*n+fa[p]);
          //  cout<<"add_2 "<<cap[i]<<" "<<dep*n+fa[p]<<'\n';
            have[p]=1; p=fa[p];
        }
    }
    for (auto i:sub_path){
        sub_col[cap[i]]--;
        have[i]=0;
    }
}
void Cut(int p,int lp,int dep){
    path.clear();
  //  cout<<p<<" "<<lp<<" "<<dep<<'\n';
    int sz=dfs1(p,lp);
    int mid=get_centroid(p,lp,sz);
  //  cout<<mid<<" : \n";
    vis[mid]=1; have[mid]=1;
    scc.add_edge(dep*n+mid,cap[mid]);
 //   cout<<"add1 "<<dep*n+mid<<" "<<cap[mid]<<'\n';
    for (auto i:path)
        all_col[cap[i]]++;
 //   cout<<"all_col ";
  //  for (int i=1;i<=k;i++)
  //      cout<<all_col[i]<<" ";
  //  cout<<'\n';
    for (auto i:g[mid]){
        if (vis[i]) continue;
        dfs2(i,mid);
        build(i,dep);
        sub_path.clear();
    }
    for (auto i:path)
        all_col[cap[i]]--;
    have[mid]=0;
    for (auto i:g[mid]){
        if (!vis[i])
            Cut(i,mid,dep+1);
    }
}
signed main(){
    fast
    cin>>n>>k;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1;i<=n;i++)
        cin>>cap[i];
    Cut(1,0,1);
    for (int i=1;i<=28*n;i++){
        if (!scc.dfn[i])
            scc.tarjan(i);
    }
    scc.build();
    int ans=k;
    for (int i=1;i<=k;i++){
  //      cout<<scc.boss[i]<<" "<<scc.dfs(scc.boss[i])<<'\n';
        ans=min(scc.dfs(scc.boss[i]),ans);
    }
    cout<<ans-1<<'\n';
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 146000 KB Output is correct
2 Correct 65 ms 146008 KB Output is correct
3 Correct 64 ms 145996 KB Output is correct
4 Correct 71 ms 145984 KB Output is correct
5 Correct 66 ms 145996 KB Output is correct
6 Correct 65 ms 145984 KB Output is correct
7 Correct 70 ms 145896 KB Output is correct
8 Correct 65 ms 145980 KB Output is correct
9 Correct 69 ms 145936 KB Output is correct
10 Correct 72 ms 145896 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 146000 KB Output is correct
2 Correct 65 ms 146008 KB Output is correct
3 Correct 64 ms 145996 KB Output is correct
4 Correct 71 ms 145984 KB Output is correct
5 Correct 66 ms 145996 KB Output is correct
6 Correct 65 ms 145984 KB Output is correct
7 Correct 70 ms 145896 KB Output is correct
8 Correct 65 ms 145980 KB Output is correct
9 Correct 69 ms 145936 KB Output is correct
10 Correct 72 ms 145896 KB Output is correct
11 Correct 69 ms 147472 KB Output is correct
12 Correct 75 ms 147420 KB Output is correct
13 Correct 77 ms 147484 KB Output is correct
14 Correct 76 ms 147452 KB Output is correct
15 Incorrect 72 ms 147616 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1406 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 146000 KB Output is correct
2 Correct 65 ms 146008 KB Output is correct
3 Correct 64 ms 145996 KB Output is correct
4 Correct 71 ms 145984 KB Output is correct
5 Correct 66 ms 145996 KB Output is correct
6 Correct 65 ms 145984 KB Output is correct
7 Correct 70 ms 145896 KB Output is correct
8 Correct 65 ms 145980 KB Output is correct
9 Correct 69 ms 145936 KB Output is correct
10 Correct 72 ms 145896 KB Output is correct
11 Correct 69 ms 147472 KB Output is correct
12 Correct 75 ms 147420 KB Output is correct
13 Correct 77 ms 147484 KB Output is correct
14 Correct 76 ms 147452 KB Output is correct
15 Incorrect 72 ms 147616 KB Output isn't correct
16 Halted 0 ms 0 KB -