Submission #1369366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369366		igofan	Mergers (JOI19_mergers)	C++20	Compilation error	0 ms	0 KiB

mergers

//Clemence's code
#include<bits/stdc++.h>
using namespace std;

vector<int> t, depth;
vector<vector<int>> adj, col, par;

void dfs(int node, int prev, int d) {
    depth[node]=d;
    par[node][0]=prev;
    col[t[node]].push_back(node);
    for(auto child : adj[node]) if(child != prev) dfs(child, node, d+1);
}

int ancestor(int x, int k) {
    int cnt=0;
    while(k&&x) {
        if(k&1) x=par[x][cnt];
        k=k>>1; cnt++;
    }
    return x;
}

int lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
    a=ancestor(a, depth[a]-depth[b]);
    if(a == b) return a;
    for(int k=19; k>=0; k--) {
        int aa=par[a][k];
        int bb=par[b][k];
        if(aa != bb) {
            a=aa; b=bb;
        }
    }
    return par[a][0];
}

struct DSU{
    vector<int> e;
    DSU(int N) {e=vector<int>(N, -1);}
    int get(int x) {return e[x] < 0 ? x : e[x]=get(e[x]);}
    int size(int x) {return -e[get(x)];}
    bool unite(int a, int b) {
        a=get(a); b=get(b);
        if(a == b) return false;
        if(e[a] > e[b]) swap(a, b);
        e[a]+=e[b]; e[b]=a;
        return true;
    }
};

void up(int node, int tar, DSU&dsu) {
    while(node != tar) {
        dsu.unite(node, par[node][0]);
        node=par[node][0];
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int n, k; cin >> n >> k;
    adj=vector<vector<int>>(n+1);
    for(int i=1; i<n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    t=depth=vector<int>(n+1);
    for(int i=1; i<=n; i++) cin >> t[i]; 
    col=vector<vector<int>>(k+1);
    par=vector<vector<int>>(n+1, vector<int>(20, 0));
    dfs(1, 0, 0);
    for(int j=1; j<20; j++) {
        for(int i=1; i<=n; i++) {
            if(par[i][j-1]) par[i][j]=par[par[i][j-1]][j-1];
        }
    }

    DSU dsu(n+1);
    for(int i=1; i<=k; i++) {
        int top=col[i][0];
        for(int j=1; j<col[i].size(); j++) top=lca(top, col[i][j]);
        for(int j=0; j<col[i].size(); j++) up(col[i][j], top, dsu);
    }

    vector<int> componentIds(n+1);
    for(int i=1; i<=n; i++) {
        componentIds[i] = dsu.get(i);
    }

    vector<vector<int>> newAdj(n+1);
    for(int i=1; i<=n; i++) {
        for(auto x : adj[i]) {
            int ii=componentIds[i], xx=componentIds[x];
            if(ii != xx) {
                newAdj[ii].push_back(xx);
            }
        }
    }

    int leaves=0;
    for(int i=1; i<=n; i++) {
        if(newAdj[i].size() == 1) leaves++;
    }
    cout << (leaves+1)/2;
    return 0;
}//Clemence's code
#include<bits/stdc++.h>
using namespace std;

vector<int> t, depth;
vector<vector<int>> adj, col, par;

void dfs(int node, int prev, int d) {
    depth[node]=d;
    par[node][0]=prev;
    col[t[node]].push_back(node);
    for(auto child : adj[node]) if(child != prev) dfs(child, node, d+1);
}

int ancestor(int x, int k) {
    int cnt=0;
    while(k&&x) {
        if(k&1) x=par[x][cnt];
        k=k>>1; cnt++;
    }
    return x;
}

int lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
    a=ancestor(a, depth[a]-depth[b]);
    if(a == b) return a;
    for(int k=19; k>=0; k--) {
        int aa=par[a][k];
        int bb=par[b][k];
        if(aa != bb) {
            a=aa; b=bb;
        }
    }
    return par[a][0];
}

struct DSU{
    vector<int> e;
    DSU(int N) {e=vector<int>(N, -1);}
    int get(int x) {return e[x] < 0 ? x : e[x]=get(e[x]);}
    int size(int x) {return -e[get(x)];}
    bool unite(int a, int b) {
        a=get(a); b=get(b);
        if(a == b) return false;
        if(e[a] > e[b]) swap(a, b);
        e[a]+=e[b]; e[b]=a;
        return true;
    }
};

void up(int node, int tar, DSU&dsu) {
    while(node != tar) {
        dsu.unite(node, par[node][0]);
        node=par[node][0];
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int n, k; cin >> n >> k;
    adj=vector<vector<int>>(n+1);
    for(int i=1; i<n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    t=depth=vector<int>(n+1);
    for(int i=1; i<=n; i++) cin >> t[i]; 
    col=vector<vector<int>>(k+1);
    par=vector<vector<int>>(n+1, vector<int>(20, 0));
    dfs(1, 0, 0);
    for(int j=1; j<20; j++) {
        for(int i=1; i<=n; i++) {
            if(par[i][j-1]) par[i][j]=par[par[i][j-1]][j-1];
        }
    }

    DSU dsu(n+1);
    for(int i=1; i<=k; i++) {
        int top=col[i][0];
        for(int j=1; j<col[i].size(); j++) top=lca(top, col[i][j]);
        for(int j=0; j<col[i].size(); j++) up(col[i][j], top, dsu);
    }

    vector<int> componentIds(n+1);
    for(int i=1; i<=n; i++) {
        componentIds[i] = dsu.get(i);
    }

    vector<vector<int>> newAdj(n+1);
    for(int i=1; i<=n; i++) {
        for(auto x : adj[i]) {
            int ii=componentIds[i], xx=componentIds[x];
            if(ii != xx) {
                newAdj[ii].push_back(xx);
            }
        }
    }

    int leaves=0;
    for(int i=1; i<=n; i++) {
        if(newAdj[i].size() == 1) leaves++;
    }
    cout << (leaves+1)/2;
    return 0;
}

Compilation message (stderr)

mergers.cpp:112:13: error: redefinition of 'std::vector<int> t'
  112 | vector<int> t, depth;
      |             ^
mergers.cpp:5:13: note: 'std::vector<int> t' previously defined here
    5 | vector<int> t, depth;
      |             ^
mergers.cpp:112:16: error: redefinition of 'std::vector<int> depth'
  112 | vector<int> t, depth;
      |                ^~~~~
mergers.cpp:5:16: note: 'std::vector<int> depth' previously defined here
    5 | vector<int> t, depth;
      |                ^~~~~
mergers.cpp:113:21: error: redefinition of 'std::vector<std::vector<int> > adj'
  113 | vector<vector<int>> adj, col, par;
      |                     ^~~
mergers.cpp:6:21: note: 'std::vector<std::vector<int> > adj' previously defined here
    6 | vector<vector<int>> adj, col, par;
      |                     ^~~
mergers.cpp:113:26: error: redefinition of 'std::vector<std::vector<int> > col'
  113 | vector<vector<int>> adj, col, par;
      |                          ^~~
mergers.cpp:6:26: note: 'std::vector<std::vector<int> > col' previously defined here
    6 | vector<vector<int>> adj, col, par;
      |                          ^~~
mergers.cpp:113:31: error: redefinition of 'std::vector<std::vector<int> > par'
  113 | vector<vector<int>> adj, col, par;
      |                               ^~~
mergers.cpp:6:31: note: 'std::vector<std::vector<int> > par' previously defined here
    6 | vector<vector<int>> adj, col, par;
      |                               ^~~
mergers.cpp:115:6: error: redefinition of 'void dfs(int, int, int)'
  115 | void dfs(int node, int prev, int d) {
      |      ^~~
mergers.cpp:8:6: note: 'void dfs(int, int, int)' previously defined here
    8 | void dfs(int node, int prev, int d) {
      |      ^~~
mergers.cpp:122:5: error: redefinition of 'int ancestor(int, int)'
  122 | int ancestor(int x, int k) {
      |     ^~~~~~~~
mergers.cpp:15:5: note: 'int ancestor(int, int)' previously defined here
   15 | int ancestor(int x, int k) {
      |     ^~~~~~~~
mergers.cpp:131:5: error: redefinition of 'int lca(int, int)'
  131 | int lca(int a, int b) {
      |     ^~~
mergers.cpp:24:5: note: 'int lca(int, int)' previously defined here
   24 | int lca(int a, int b) {
      |     ^~~
mergers.cpp:145:8: error: redefinition of 'struct DSU'
  145 | struct DSU{
      |        ^~~
mergers.cpp:38:8: note: previous definition of 'struct DSU'
   38 | struct DSU{
      |        ^~~
mergers.cpp:159:6: error: redefinition of 'void up(int, int, DSU&)'
  159 | void up(int node, int tar, DSU&dsu) {
      |      ^~
mergers.cpp:52:6: note: 'void up(int, int, DSU&)' previously defined here
   52 | void up(int node, int tar, DSU&dsu) {
      |      ^~
mergers.cpp:166:8: error: redefinition of 'int main()'
  166 | signed main() {
      |        ^~~~
mergers.cpp:59:8: note: 'int main()' previously defined here
   59 | signed main() {
      |        ^~~~