oj.uz

Submission #676768

# Submission time Handle Problem Language Result Execution time Memory
676768 2023-01-01T04:19:45 Z victor_gao Capital City (JOI20_capital_city) C++17
100 / 100
 2180 ms 469440 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];
    long long 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);
            dp[p]=min(dp[p],1000000LL);
        }
        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 112 ms 249596 KB Output is correct
2 Correct 106 ms 249576 KB Output is correct
3 Correct 109 ms 249676 KB Output is correct
4 Correct 119 ms 249604 KB Output is correct
5 Correct 112 ms 249600 KB Output is correct
6 Correct 112 ms 249676 KB Output is correct
7 Correct 107 ms 249648 KB Output is correct
8 Correct 119 ms 249632 KB Output is correct
9 Correct 107 ms 249712 KB Output is correct
10 Correct 108 ms 249608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 249596 KB Output is correct
2 Correct 106 ms 249576 KB Output is correct
3 Correct 109 ms 249676 KB Output is correct
4 Correct 119 ms 249604 KB Output is correct
5 Correct 112 ms 249600 KB Output is correct
6 Correct 112 ms 249676 KB Output is correct
7 Correct 107 ms 249648 KB Output is correct
8 Correct 119 ms 249632 KB Output is correct
9 Correct 107 ms 249712 KB Output is correct
10 Correct 108 ms 249608 KB Output is correct
11 Correct 114 ms 250540 KB Output is correct
12 Correct 112 ms 250524 KB Output is correct
13 Correct 125 ms 250608 KB Output is correct
14 Correct 120 ms 250456 KB Output is correct
15 Correct 113 ms 250800 KB Output is correct
16 Correct 112 ms 250696 KB Output is correct
17 Correct 113 ms 250664 KB Output is correct
18 Correct 114 ms 250600 KB Output is correct
19 Correct 121 ms 250644 KB Output is correct
20 Correct 112 ms 250600 KB Output is correct
21 Correct 120 ms 250640 KB Output is correct
22 Correct 110 ms 250912 KB Output is correct
23 Correct 112 ms 250872 KB Output is correct
24 Correct 116 ms 250752 KB Output is correct
25 Correct 128 ms 250992 KB Output is correct
26 Correct 114 ms 251028 KB Output is correct
27 Correct 115 ms 251036 KB Output is correct
28 Correct 115 ms 250980 KB Output is correct
29 Correct 114 ms 251020 KB Output is correct
30 Correct 113 ms 250976 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1862 ms 442576 KB Output is correct
2 Correct 637 ms 442996 KB Output is correct
3 Correct 1918 ms 446052 KB Output is correct
4 Correct 636 ms 446708 KB Output is correct
5 Correct 1869 ms 448152 KB Output is correct
6 Correct 644 ms 447248 KB Output is correct
7 Correct 1831 ms 452528 KB Output is correct
8 Correct 686 ms 456800 KB Output is correct
9 Correct 2123 ms 464552 KB Output is correct
10 Correct 2134 ms 464116 KB Output is correct
11 Correct 2180 ms 464968 KB Output is correct
12 Correct 2126 ms 467656 KB Output is correct
13 Correct 2148 ms 461892 KB Output is correct
14 Correct 2101 ms 467392 KB Output is correct
15 Correct 2036 ms 464976 KB Output is correct
16 Correct 2032 ms 462692 KB Output is correct
17 Correct 2031 ms 463276 KB Output is correct
18 Correct 2057 ms 462932 KB Output is correct
19 Correct 2101 ms 465036 KB Output is correct
20 Correct 2037 ms 469440 KB Output is correct
21 Correct 110 ms 249588 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 249596 KB Output is correct
2 Correct 106 ms 249576 KB Output is correct
3 Correct 109 ms 249676 KB Output is correct
4 Correct 119 ms 249604 KB Output is correct
5 Correct 112 ms 249600 KB Output is correct
6 Correct 112 ms 249676 KB Output is correct
7 Correct 107 ms 249648 KB Output is correct
8 Correct 119 ms 249632 KB Output is correct
9 Correct 107 ms 249712 KB Output is correct
10 Correct 108 ms 249608 KB Output is correct
11 Correct 114 ms 250540 KB Output is correct
12 Correct 112 ms 250524 KB Output is correct
13 Correct 125 ms 250608 KB Output is correct
14 Correct 120 ms 250456 KB Output is correct
15 Correct 113 ms 250800 KB Output is correct
16 Correct 112 ms 250696 KB Output is correct
17 Correct 113 ms 250664 KB Output is correct
18 Correct 114 ms 250600 KB Output is correct
19 Correct 121 ms 250644 KB Output is correct
20 Correct 112 ms 250600 KB Output is correct
21 Correct 120 ms 250640 KB Output is correct
22 Correct 110 ms 250912 KB Output is correct
23 Correct 112 ms 250872 KB Output is correct
24 Correct 116 ms 250752 KB Output is correct
25 Correct 128 ms 250992 KB Output is correct
26 Correct 114 ms 251028 KB Output is correct
27 Correct 115 ms 251036 KB Output is correct
28 Correct 115 ms 250980 KB Output is correct
29 Correct 114 ms 251020 KB Output is correct
30 Correct 113 ms 250976 KB Output is correct
31 Correct 1862 ms 442576 KB Output is correct
32 Correct 637 ms 442996 KB Output is correct
33 Correct 1918 ms 446052 KB Output is correct
34 Correct 636 ms 446708 KB Output is correct
35 Correct 1869 ms 448152 KB Output is correct
36 Correct 644 ms 447248 KB Output is correct
37 Correct 1831 ms 452528 KB Output is correct
38 Correct 686 ms 456800 KB Output is correct
39 Correct 2123 ms 464552 KB Output is correct
40 Correct 2134 ms 464116 KB Output is correct
41 Correct 2180 ms 464968 KB Output is correct
42 Correct 2126 ms 467656 KB Output is correct
43 Correct 2148 ms 461892 KB Output is correct
44 Correct 2101 ms 467392 KB Output is correct
45 Correct 2036 ms 464976 KB Output is correct
46 Correct 2032 ms 462692 KB Output is correct
47 Correct 2031 ms 463276 KB Output is correct
48 Correct 2057 ms 462932 KB Output is correct
49 Correct 2101 ms 465036 KB Output is correct
50 Correct 2037 ms 469440 KB Output is correct
51 Correct 110 ms 249588 KB Output is correct
52 Correct 1172 ms 367532 KB Output is correct
53 Correct 1255 ms 375288 KB Output is correct
54 Correct 1199 ms 373780 KB Output is correct
55 Correct 1220 ms 376300 KB Output is correct
56 Correct 1321 ms 375996 KB Output is correct
57 Correct 1247 ms 373592 KB Output is correct
58 Correct 1625 ms 431672 KB Output is correct
59 Correct 1574 ms 423784 KB Output is correct
60 Correct 1613 ms 420040 KB Output is correct
61 Correct 1716 ms 427636 KB Output is correct
62 Correct 659 ms 446828 KB Output is correct
63 Correct 634 ms 446800 KB Output is correct
64 Correct 674 ms 454480 KB Output is correct
65 Correct 633 ms 447504 KB Output is correct
66 Correct 1128 ms 400068 KB Output is correct
67 Correct 1122 ms 399968 KB Output is correct
68 Correct 1117 ms 400052 KB Output is correct
69 Correct 1155 ms 400124 KB Output is correct
70 Correct 1130 ms 399980 KB Output is correct
71 Correct 1118 ms 399912 KB Output is correct
72 Correct 1149 ms 399896 KB Output is correct
73 Correct 1168 ms 399336 KB Output is correct
74 Correct 1191 ms 400108 KB Output is correct
75 Correct 1113 ms 399972 KB Output is correct
76 Correct 1675 ms 431428 KB Output is correct
77 Correct 1735 ms 427276 KB Output is correct
78 Correct 2065 ms 461744 KB Output is correct
79 Correct 2023 ms 460848 KB Output is correct
80 Correct 2160 ms 467864 KB Output is correct
81 Correct 2070 ms 464096 KB Output is correct
82 Correct 2076 ms 464184 KB Output is correct
83 Correct 2080 ms 461768 KB Output is correct
84 Correct 2064 ms 465736 KB Output is correct
85 Correct 2079 ms 466116 KB Output is correct
86 Correct 2080 ms 460856 KB Output is correct
87 Correct 2056 ms 462812 KB Output is correct
88 Correct 1930 ms 456012 KB Output is correct
89 Correct 1889 ms 455976 KB Output is correct
90 Correct 1884 ms 455788 KB Output is correct
91 Correct 1825 ms 456672 KB Output is correct
92 Correct 1897 ms 454976 KB Output is correct
93 Correct 1859 ms 456628 KB Output is correct
94 Correct 1869 ms 455812 KB Output is correct
95 Correct 1860 ms 456400 KB Output is correct
96 Correct 1945 ms 454900 KB Output is correct
97 Correct 1891 ms 457052 KB Output is correct