oj.uz

Submission #280055

# Submission time Handle Problem Language Result Execution time Memory
280055 2020-08-22T13:04:44 Z 3zp Mergers (JOI19_mergers) C++14
0 / 100
 180 ms 18032 KB 
#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], Nice[mN], Good[mN], Deg[mN], Sz[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(Good[x] || (Sz[x] > 0 && Sz[x] < good_cnt)){
        Deg[x]++;
        Deg[p]++;
    }
}
main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        cin >> 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;
    }
    int cnt = 0;
    Nice[0] = 1;
    for(int i = 1; i <= n; i++){
        int u = S[A[i]];
        if(St[u] == i) cnt ++;
        if(En[u] == i) cnt --;
        if(cnt == 0) Nice[i] = 1;
    }
    for(int i = 1; i <= n; i++){
        if(Nice[L[i] - 1] && Nice[R[i]])
            Good[i] = 1,
            good_cnt ++;
    }
    dfs2(1, 0);
    int leaf_cnt = 0;
    for(int i = 1; i <= n; i++)
        if(Deg[i] == 1) leaf_cnt++;
    cout << (leaf_cnt + 1) / 2 << endl;
}

Compilation message

mergers.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      |      ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 8 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Incorrect 8 ms 12160 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 8 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Incorrect 8 ms 12160 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 8 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Incorrect 8 ms 12160 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 18032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 8 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Incorrect 8 ms 12160 KB Output isn't correct
6 Halted 0 ms 0 KB -