oj.uz

Submission #676760

# Submission time Handle Problem Language Result Execution time Memory
676760 2023-01-01T03:51:25 Z victor_gao Capital City (JOI20_capital_city) C++17
1 / 100
 1631 ms 325992 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
#define C 25
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[C*N];
    vector<pii>edge;
    int dfn[C*N],low[C*N],dft=0,boss[C*N],val[C*N],dp[C*N],nscc=0;
    bool ins[C*N],vis[C*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<C*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';
        scc.add_edge(cap[i],dep*n+fa[p]);
        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]]--;
}
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){
        have[i]=0;
        all_col[cap[i]]--;
    }
    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<=k;i++){
        if (!scc.dfn[i])
            scc.tarjan(i);
    }
    scc.build();
    int ans=1e9;
    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);
    }
    assert(ans<=k);
    cout<<ans-1<<'\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122456 KB Output is correct
2 Correct 55 ms 122508 KB Output is correct
3 Correct 54 ms 122420 KB Output is correct
4 Correct 55 ms 122416 KB Output is correct
5 Correct 67 ms 122444 KB Output is correct
6 Correct 59 ms 122444 KB Output is correct
7 Correct 60 ms 122548 KB Output is correct
8 Correct 56 ms 122536 KB Output is correct
9 Correct 56 ms 122456 KB Output is correct
10 Correct 56 ms 122568 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122456 KB Output is correct
2 Correct 55 ms 122508 KB Output is correct
3 Correct 54 ms 122420 KB Output is correct
4 Correct 55 ms 122416 KB Output is correct
5 Correct 67 ms 122444 KB Output is correct
6 Correct 59 ms 122444 KB Output is correct
7 Correct 60 ms 122548 KB Output is correct
8 Correct 56 ms 122536 KB Output is correct
9 Correct 56 ms 122456 KB Output is correct
10 Correct 56 ms 122568 KB Output is correct
11 Correct 60 ms 123512 KB Output is correct
12 Correct 59 ms 123588 KB Output is correct
13 Correct 58 ms 123592 KB Output is correct
14 Correct 66 ms 123648 KB Output is correct
15 Incorrect 61 ms 123720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1631 ms 322052 KB Output is correct
2 Incorrect 594 ms 325992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122456 KB Output is correct
2 Correct 55 ms 122508 KB Output is correct
3 Correct 54 ms 122420 KB Output is correct
4 Correct 55 ms 122416 KB Output is correct
5 Correct 67 ms 122444 KB Output is correct
6 Correct 59 ms 122444 KB Output is correct
7 Correct 60 ms 122548 KB Output is correct
8 Correct 56 ms 122536 KB Output is correct
9 Correct 56 ms 122456 KB Output is correct
10 Correct 56 ms 122568 KB Output is correct
11 Correct 60 ms 123512 KB Output is correct
12 Correct 59 ms 123588 KB Output is correct
13 Correct 58 ms 123592 KB Output is correct
14 Correct 66 ms 123648 KB Output is correct
15 Incorrect 61 ms 123720 KB Output isn't correct
16 Halted 0 ms 0 KB -