Submission #280106

#	Time	Username	Problem	Language	Result	Execution time	Memory
280106		3zp	Mergers (JOI19_mergers)	C++14	100 / 100	982 ms	71404 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int mN = 500009;
vector<int> V[mN];
int L[mN],R[mN], A[mN], St[mN], En[mN], S[mN], Good[mN], Deg[mN], Sz[mN], Min[mN], Max[mN];
int c = 1;
int good_cnt = 0;
void dfs1(int x, int p){
    L[x] = c;
    R[x] = c;
    A[c] = x;
    c++;
    for(int y : V[x]){
        if(y == p) continue;
        dfs1(y, x);
        R[x] = R[y];
    }
}
void dfs2(int x, int p){
    if(Good[x]) Sz[x] = 1;
    for(int y : V[x]){
        if(y == p) continue;
        dfs2(y, x);
        Sz[x] += Sz[y];
    }

    if(x > 1 && (Good[x] || (Sz[x] > 0 && Sz[x] < good_cnt))){
        Deg[x]++;
        Deg[p]++;
    }
}
void dfs3(int x, int p){
    Min[x] = St[S[x]];
    Max[x] = En[S[x]];
    for(int y : V[x]){
        if(y == p) continue;
        dfs3(y, x);
        Min[x] = min(Min[x], Min[y]);
        Max[x] = max(Max[x], Max[y]);
    }
    if(x > 1 && Min[x] == L[x] && Max[x] == R[x]){
        Good[x] = 1;
        good_cnt++;
    }

}
main(){

    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 1; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        V[a].push_back(b);
        V[b].push_back(a);
    }
    for(int i = 1; i <= n; i++)
        scanf("%d", &S[i]);
    dfs1(1, 0);
    for(int i = 1; i <= n; i++){
        int x = A[i];
        if(!St[S[x]]) St[S[x]] = i;
        En[S[x]] = i;
    }
    dfs3(1, 0);
    dfs2(1, 0);
    int leaf_cnt = 0;
    for(int i = 1; i <= n; i++)
        if(Deg[i] == 1) leaf_cnt++;
    printf("%d\n", (leaf_cnt + 1) / 2 );
}

Compilation message (stderr)

mergers.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      |      ^
mergers.cpp: In function 'int main()':
mergers.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d", &S[i]);
      |         ~~~~~^~~~~~~~~~~~~

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