oj.uz

Submission #676759

# Submission time Handle Problem Language Result Execution time Memory
676759 2023-01-01T03:49:34 Z victor_gao Capital City (JOI20_capital_city) C++17
1 / 100
 1659 ms 320496 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';
        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 122480 KB Output is correct
2 Correct 55 ms 122416 KB Output is correct
3 Correct 57 ms 122416 KB Output is correct
4 Correct 57 ms 122472 KB Output is correct
5 Correct 56 ms 122528 KB Output is correct
6 Correct 59 ms 122444 KB Output is correct
7 Correct 56 ms 122432 KB Output is correct
8 Correct 57 ms 122632 KB Output is correct
9 Correct 57 ms 122420 KB Output is correct
10 Correct 59 ms 122464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122480 KB Output is correct
2 Correct 55 ms 122416 KB Output is correct
3 Correct 57 ms 122416 KB Output is correct
4 Correct 57 ms 122472 KB Output is correct
5 Correct 56 ms 122528 KB Output is correct
6 Correct 59 ms 122444 KB Output is correct
7 Correct 56 ms 122432 KB Output is correct
8 Correct 57 ms 122632 KB Output is correct
9 Correct 57 ms 122420 KB Output is correct
10 Correct 59 ms 122464 KB Output is correct
11 Correct 62 ms 123508 KB Output is correct
12 Correct 70 ms 123480 KB Output is correct
13 Correct 61 ms 123460 KB Output is correct
14 Correct 61 ms 123476 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 Incorrect 1659 ms 320496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122480 KB Output is correct
2 Correct 55 ms 122416 KB Output is correct
3 Correct 57 ms 122416 KB Output is correct
4 Correct 57 ms 122472 KB Output is correct
5 Correct 56 ms 122528 KB Output is correct
6 Correct 59 ms 122444 KB Output is correct
7 Correct 56 ms 122432 KB Output is correct
8 Correct 57 ms 122632 KB Output is correct
9 Correct 57 ms 122420 KB Output is correct
10 Correct 59 ms 122464 KB Output is correct
11 Correct 62 ms 123508 KB Output is correct
12 Correct 70 ms 123480 KB Output is correct
13 Correct 61 ms 123460 KB Output is correct
14 Correct 61 ms 123476 KB Output is correct
15 Incorrect 61 ms 123720 KB Output isn't correct
16 Halted 0 ms 0 KB -