Submission #563776

#	Time	Username	Problem	Language	Result	Execution time	Memory
563776		tqbfjotld	Mergers (JOI19_mergers)	C++14	100 / 100	1137 ms	143332 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

int p[500005][20];
int dep[500005];

vector<int> adjl[500005];

void dfs(int node, int pa){
    p[node][0] = pa;
    for (auto x : adjl[node]){
        if (x==pa) continue;
        dep[x] = dep[node]+1;
        dfs(x,node);
    }
}

int lca(int a, int b){
    if (dep[a]>dep[b]){
        swap(a,b);
    }
    int t = dep[b]-dep[a];
    for (int x = 0; x<20; x++){
        if (t&(1<<x)){
            b = p[b][x];
        }
    }
    if (a==b) return a;
    for (int x = 19; x>=0; x--){
        if (p[a][x]!=p[b][x]){
            a = p[a][x];
            b = p[b][x];
        }
    }
    return p[a][0];
}

int arr[500005];
vector<int> states[500005];

int pa[500005];
int rt(int a){return pa[a]==a?a:pa[a]=rt(pa[a]);}
void mer(int a, int b){
    a = rt(a);
    b = rt(b);
    if (a==b) return;
    pa[a] = b;
}

int dfs2(int node, int np){
    int num = arr[node];
    for (auto x : adjl[node]){
        if (x==np) continue;
        num += dfs2(x,node);
    }
    if (num>0){
        mer(node,np);
    }
    return num;
}

vector<int> adjl2[500005];

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for (int x = 0; x<n-1; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        adjl[a].push_back(b);
        adjl[b].push_back(a);
    }
    dfs(1,0);
    for (int x = 1; x<20; x++){
        for (int y = 0; y<=n; y++){
            p[y][x] = p[p[y][x-1]][x-1];
        }
    }
    for (int x = 1; x<=n; x++){
        int a;
        scanf("%d",&a);
        states[a].push_back(x);
    }
    for (int x = 1; x<=k; x++){
        if (states[x].empty()) continue;
        int cur = states[x][0];
        for (int y = 1; y<states[x].size(); y++){
            arr[cur]++;
            arr[states[x][y]]++;
            int t = lca(cur,states[x][y]);
            //printf("lca = %d\n",t);
            arr[t]-=2;
            cur = states[x][y];
        }
    }
    for (int x = 0; x<=n; x++){
        pa[x] = x;
    }
    dfs2(1,0);
    int z = 0;
    for (int x = 2; x<=n; x++){
        if (rt(p[x][0])!=rt(x)){
            adjl2[rt(x)].push_back(rt(p[x][0]));
            adjl2[rt(p[x][0])].push_back(rt(x));
            z++;
            //printf("z %d %d\n",rt(x),rt(p[x][0]));
        }
    }
    if (z==0){
        printf("0");
        return 0;
    }
    int t2 = 0;
    for (int x = 1; x<=n; x++){
        if (adjl2[x].size()==1){
            t2++;
        }
    }
    printf("%d",(t2+1)/2);

}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int y = 1; y<states[x].size(); y++){
      |                         ~^~~~~~~~~~~~~~~~~
mergers.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
mergers.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
mergers.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30