oj.uz

Submission #676767

# Submission time Handle Problem Language Result Execution time Memory
676767 2023-01-01T04:17:54 Z victor_gao Capital City (JOI20_capital_city) C++17
1 / 100
 1860 ms 424216 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 init(){
        edge.clear();
        while (!st.empty()) st.pop();
        for (int i=0;i<C*N;i++){
            dfn[i]=low[i]=boss[i]=val[i]=dp[i]=0;
            g[i].clear();
            ins[i]=vis[i]=0;
        }
    }
    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;
    scc.init();
    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 100 ms 230004 KB Output is correct
2 Correct 104 ms 229992 KB Output is correct
3 Correct 105 ms 230092 KB Output is correct
4 Correct 107 ms 230108 KB Output is correct
5 Correct 101 ms 230024 KB Output is correct
6 Correct 102 ms 230112 KB Output is correct
7 Correct 107 ms 230016 KB Output is correct
8 Correct 109 ms 230028 KB Output is correct
9 Correct 101 ms 230004 KB Output is correct
10 Correct 101 ms 230092 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 230004 KB Output is correct
2 Correct 104 ms 229992 KB Output is correct
3 Correct 105 ms 230092 KB Output is correct
4 Correct 107 ms 230108 KB Output is correct
5 Correct 101 ms 230024 KB Output is correct
6 Correct 102 ms 230112 KB Output is correct
7 Correct 107 ms 230016 KB Output is correct
8 Correct 109 ms 230028 KB Output is correct
9 Correct 101 ms 230004 KB Output is correct
10 Correct 101 ms 230092 KB Output is correct
11 Correct 106 ms 230956 KB Output is correct
12 Correct 108 ms 231148 KB Output is correct
13 Correct 105 ms 230984 KB Output is correct
14 Correct 117 ms 230880 KB Output is correct
15 Incorrect 118 ms 231064 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1860 ms 424216 KB Output is correct
2 Incorrect 625 ms 423676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 230004 KB Output is correct
2 Correct 104 ms 229992 KB Output is correct
3 Correct 105 ms 230092 KB Output is correct
4 Correct 107 ms 230108 KB Output is correct
5 Correct 101 ms 230024 KB Output is correct
6 Correct 102 ms 230112 KB Output is correct
7 Correct 107 ms 230016 KB Output is correct
8 Correct 109 ms 230028 KB Output is correct
9 Correct 101 ms 230004 KB Output is correct
10 Correct 101 ms 230092 KB Output is correct
11 Correct 106 ms 230956 KB Output is correct
12 Correct 108 ms 231148 KB Output is correct
13 Correct 105 ms 230984 KB Output is correct
14 Correct 117 ms 230880 KB Output is correct
15 Incorrect 118 ms 231064 KB Output isn't correct
16 Halted 0 ms 0 KB -