Submission #1315887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315887		aaaaaaaa	Capital City (JOI20_capital_city)	C++20	Compilation error	0 ms	0 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 100;
vector<int> adj[mxN], col[mxN];
int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
void dfs(int u, int par){
    parent[u] = par;
    for(auto it : adj[u]){
        if(!vis[it] && it ^ par && !vis_col[id[it]]) dfs(it, u);
    }
}
void calc_sz(int u, int par){
    sz[u] = 1;
    for(auto it : adj[u]){
        if(!vis[it] && it ^ par && !vis_col[id[it]]){
            calc_sz(it, u);
            sz[u] += sz[it];
        }
    }
}
int find_cent(int u, int par, int nby2){
    for(auto it : adj[u]){
        if(!vis[it] && it ^ par && !vis_col[id[it]] && sz[it] >= nby2){
            return find_cent(it, u, nby2);
        }
    }
    return u;
}
void decompose(int u = 1, int par = -1){
    calc_sz(u, -1);
    int cent = find_cent(u, -1, sz[u] / 2);
    dfs(cent, -1);

    queue<int> q;

    q.push(id[cent]);

    vector<int> cvis(k + 1, 0);

    int cans = 0;

    while(q.size()){
        auto tp = q.front();
        q.pop();
        if(vis_col[tp]){
            cans = mxN;
            break;
        }
        if(cvis[tp]) continue;
        cvis[tp] = 1;
        cans += 1;
        for(auto it : col[tp]){
            if(parent[it] != -1){
                if(vis_col[id[parent[it]]]){
                    cans = mxN;
                    break;
                }
                if(!cvis[id[parent[it]]]){
                    q.push(id[parent[it]]);
                    //cvis[id[parent[it]]] = 1;
                }
            }
        }
    }

    ans = min(ans, cans);

    vis[cent] = 1, vis_col[id[cent]] = 1;
    for(auto it : adj[cent]){
        if(!vis[it]) decompose(it, u);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k;
    for(int i = 0, u, v; i < n - 1; ++i){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1, x; i <= n; ++i){
        cin >> x; id[i] = x;
        col[x].push_back(i);
    }
    decompose();
    cout << --ans << "\n";
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 100;
vector<int> adj[mxN], col[mxN];
int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
void dfs(int u, int par){
    parent[u] = par;
    for(auto it : adj[u]){
        if(!vis[it] && it ^ par && !vis_col[id[it]]) dfs(it, u);
    }
}
void calc_sz(int u, int par){
    sz[u] = 1;
    for(auto it : adj[u]){
        if(!vis[it] && it ^ par && !vis_col[id[it]]){
            calc_sz(it, u);
            sz[u] += sz[it];
        }
    }
}
int find_cent(int u, int par, int nby2){
    for(auto it : adj[u]){
        if(!vis[it] && it ^ par && !vis_col[id[it]] && sz[it] >= nby2){
            return find_cent(it, u, nby2);
        }
    }
    return u;
}
void decompose(int u = 1, int par = -1){
    calc_sz(u, -1);
    int cent = find_cent(u, -1, sz[u] / 2);
    dfs(cent, -1);

    queue<int> q;

    q.push(id[cent]);

    vector<int> cvis(k + 1, 0);

    int cans = 0;

    while(q.size()){
        auto tp = q.front();
        q.pop();
        if(cvis[tp]) continue;
        cvis[tp] = 1;
        cans += 1;
        for(auto it : col[tp]){
            if(parent[it] != -1){
                if(vis_col[id[parent[it]]]){
                    cans = mxN;
                    break;
                }
                if(!cvis[id[parent[it]]]){
                    q.push(id[parent[it]]);
                    //cvis[id[parent[it]]] = 1;
                }
            }
        }
    }

    ans = min(ans, cans);

    vis[cent] = 1, vis_col[id[cent]] = 1;
    for(auto it : adj[cent]){
        if(!vis[it]) decompose(it, u);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k;
    for(int i = 0, u, v; i < n - 1; ++i){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1, x; i <= n; ++i){
        cin >> x; id[i] = x;
        col[x].push_back(i);
    }
    decompose();
    cout << --ans << "\n";
    return 0;
}

Compilation message (stderr)

capital_city.cpp:94:11: error: redefinition of 'const int mxN'
   94 | const int mxN = 2e5 + 100;
      |           ^~~
capital_city.cpp:4:11: note: 'const int mxN' previously defined here
    4 | const int mxN = 2e5 + 100;
      |           ^~~
capital_city.cpp:95:13: error: redefinition of 'std::vector<int> adj [200100]'
   95 | vector<int> adj[mxN], col[mxN];
      |             ^~~
capital_city.cpp:5:13: note: 'std::vector<int> adj [200100]' previously defined here
    5 | vector<int> adj[mxN], col[mxN];
      |             ^~~
capital_city.cpp:95:23: error: redefinition of 'std::vector<int> col [200100]'
   95 | vector<int> adj[mxN], col[mxN];
      |                       ^~~
capital_city.cpp:5:23: note: 'std::vector<int> col [200100]' previously defined here
    5 | vector<int> adj[mxN], col[mxN];
      |                       ^~~
capital_city.cpp:96:5: error: redefinition of 'int sz [200100]'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |     ^~
capital_city.cpp:6:5: note: 'int sz [200100]' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |     ^~
capital_city.cpp:96:14: error: redefinition of 'int vis [200100]'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |              ^~~
capital_city.cpp:6:14: note: 'int vis [200100]' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |              ^~~
capital_city.cpp:96:24: error: redefinition of 'int id [200100]'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                        ^~
capital_city.cpp:6:24: note: 'int id [200100]' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                        ^~
capital_city.cpp:96:33: error: redefinition of 'int vis_col [200100]'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                 ^~~~~~~
capital_city.cpp:6:33: note: 'int vis_col [200100]' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                 ^~~~~~~
capital_city.cpp:96:47: error: redefinition of 'int parent [200100]'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                               ^~~~~~
capital_city.cpp:6:47: note: 'int parent [200100]' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                               ^~~~~~
capital_city.cpp:96:60: error: redefinition of 'int n'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                                            ^
capital_city.cpp:6:60: note: 'int n' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                                            ^
capital_city.cpp:96:63: error: redefinition of 'int k'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                                               ^
capital_city.cpp:6:63: note: 'int k' previously declared here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                                               ^
capital_city.cpp:96:66: error: redefinition of 'int ans'
   96 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                                                  ^~~
capital_city.cpp:6:66: note: 'int ans' previously defined here
    6 | int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
      |                                                                  ^~~
capital_city.cpp:97:6: error: redefinition of 'void dfs(int, int)'
   97 | void dfs(int u, int par){
      |      ^~~
capital_city.cpp:7:6: note: 'void dfs(int, int)' previously defined here
    7 | void dfs(int u, int par){
      |      ^~~
capital_city.cpp:103:6: error: redefinition of 'void calc_sz(int, int)'
  103 | void calc_sz(int u, int par){
      |      ^~~~~~~
capital_city.cpp:13:6: note: 'void calc_sz(int, int)' previously defined here
   13 | void calc_sz(int u, int par){
      |      ^~~~~~~
capital_city.cpp:112:5: error: redefinition of 'int find_cent(int, int, int)'
  112 | int find_cent(int u, int par, int nby2){
      |     ^~~~~~~~~
capital_city.cpp:22:5: note: 'int find_cent(int, int, int)' previously defined here
   22 | int find_cent(int u, int par, int nby2){
      |     ^~~~~~~~~
capital_city.cpp:120:6: error: redefinition of 'void decompose(int, int)'
  120 | void decompose(int u = 1, int par = -1){
      |      ^~~~~~~~~
capital_city.cpp:30:6: note: 'void decompose(int, int)' previously defined here
   30 | void decompose(int u = 1, int par = -1){
      |      ^~~~~~~~~
capital_city.cpp:160:8: error: redefinition of 'int main()'
  160 | signed main(){
      |        ^~~~
capital_city.cpp:74:8: note: 'int main()' previously defined here
   74 | signed main(){
      |        ^~~~