oj.uz

Submission #163758

# Submission time Handle Problem Language Result Execution time Memory
163758 2019-11-15T07:43:36 Z georgerapeanu Mergers (JOI19_mergers) C++11
0 / 100
 160 ms 90164 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int NMAX = 5e5;
const int LGMAX = 19;

int n;
int k;

vector<int> graph[NMAX + 5];
vector<int> nodes[NMAX + 5];

int state[NMAX + 5];
int father[LGMAX + 5][NMAX + 5];
int lvl[NMAX + 5];
int merge_root[NMAX + 5];
bool seen[NMAX + 5];

void predfs(int nod,int tata){
    father[0][nod] = tata;
    merge_root[nod] = 0;
    lvl[nod] = 1 + lvl[tata];
    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }
        predfs(it,nod);
    }
}

void prelca(){
    for(int h = 1;h <= LGMAX;h++){
        for(int i = 1;i <= NMAX;i++){
            father[h][i] = father[h - 1][father[h - 1][i]];
        }
    }
}

int lca(int x,int y){
    if(lvl[x] > lvl[y]){
        swap(x,y);
    }

    int diff = lvl[y] - lvl[x];

    for(int h = LGMAX;h >= 0;h--){
        if((diff >> h) & 1){
            y = father[h][y];
        }
    }

    if(x == y){
        return x;
    }

    for(int h = LGMAX;h >= 0;h--){
        if(father[h][x] != father[h][y]){
            x = father[h][x];
            y = father[h][y];
        }
    }

    return father[0][x];
}

int col_root[NMAX + 5];

int fi_col_root(int node){
    if(col_root[node] == 0){
        return node;
    }
    return col_root[node];
}

bool merge_cols(int u,int v){
    u = fi_col_root(u);
    v = fi_col_root(v);

    if(u == v){
        return false;
    }

    col_root[v] = u;

    return true;
}

int fi_merge_root(int node){
    if(merge_root[node] == 0){
        return node;
    }
    return merge_root[node] = fi_merge_root(merge_root[node]);
}

void do_merge(int node,int root){
    node = fi_merge_root(node);
    while(lvl[root] < lvl[node]){
        merge_cols(state[node],state[father[0][node]]);
        merge_root[node] = father[0][node];
        node = fi_merge_root(node);
    }
}

set<int> col_neighbors[NMAX + 5];

int main(){

    scanf("%d %d",&n,&k);

    for(int i = 1;i < n;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for(int i = 1;i <= n;i++){
        scanf("%d",&state[i]);
        nodes[state[i]].push_back(i);
    }

    predfs(1,0);
    prelca();

    for(int i = 1;i <= k;i++){
        if(nodes[i].empty()){
            continue;
        }

        int u = nodes[i].back();

        for(auto it:nodes[i]){
            u = lca(u,it);
        }

        for(auto it:nodes[i]){
            do_merge(it,u);
        }
    }

    int cnt = 0;

    for(int col = 1;col <= k;col++){
        for(auto it:nodes[col]){
            for(auto it2:graph[it]){
                if(fi_col_root(col) != fi_col_root(state[it2])){
                    col_neighbors[fi_col_root(col)].insert(fi_col_root(state[it2]));
                }
            }
        }
    }

    for(int col = 1;col <= k;col++){
        cnt += (col_neighbors[col].size() == 1);
    }

    printf("%d\n",(cnt != 1) * (cnt + 1) / 2);
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&state[i]);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 84472 KB Output is correct
2 Correct 90 ms 84476 KB Output is correct
3 Correct 90 ms 84472 KB Output is correct
4 Correct 89 ms 84472 KB Output is correct
5 Correct 89 ms 84472 KB Output is correct
6 Correct 90 ms 84460 KB Output is correct
7 Correct 88 ms 84600 KB Output is correct
8 Correct 89 ms 84444 KB Output is correct
9 Correct 90 ms 84472 KB Output is correct
10 Correct 90 ms 84476 KB Output is correct
11 Correct 90 ms 84444 KB Output is correct
12 Correct 90 ms 84440 KB Output is correct
13 Correct 89 ms 84472 KB Output is correct
14 Correct 89 ms 84472 KB Output is correct
15 Correct 85 ms 84452 KB Output is correct
16 Correct 88 ms 84472 KB Output is correct
17 Correct 83 ms 84472 KB Output is correct
18 Correct 83 ms 84472 KB Output is correct
19 Correct 90 ms 84476 KB Output is correct
20 Correct 84 ms 84444 KB Output is correct
21 Incorrect 85 ms 84472 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 84472 KB Output is correct
2 Correct 90 ms 84476 KB Output is correct
3 Correct 90 ms 84472 KB Output is correct
4 Correct 89 ms 84472 KB Output is correct
5 Correct 89 ms 84472 KB Output is correct
6 Correct 90 ms 84460 KB Output is correct
7 Correct 88 ms 84600 KB Output is correct
8 Correct 89 ms 84444 KB Output is correct
9 Correct 90 ms 84472 KB Output is correct
10 Correct 90 ms 84476 KB Output is correct
11 Correct 90 ms 84444 KB Output is correct
12 Correct 90 ms 84440 KB Output is correct
13 Correct 89 ms 84472 KB Output is correct
14 Correct 89 ms 84472 KB Output is correct
15 Correct 85 ms 84452 KB Output is correct
16 Correct 88 ms 84472 KB Output is correct
17 Correct 83 ms 84472 KB Output is correct
18 Correct 83 ms 84472 KB Output is correct
19 Correct 90 ms 84476 KB Output is correct
20 Correct 84 ms 84444 KB Output is correct
21 Incorrect 85 ms 84472 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 84472 KB Output is correct
2 Correct 90 ms 84476 KB Output is correct
3 Correct 90 ms 84472 KB Output is correct
4 Correct 89 ms 84472 KB Output is correct
5 Correct 89 ms 84472 KB Output is correct
6 Correct 90 ms 84460 KB Output is correct
7 Correct 88 ms 84600 KB Output is correct
8 Correct 89 ms 84444 KB Output is correct
9 Correct 90 ms 84472 KB Output is correct
10 Correct 90 ms 84476 KB Output is correct
11 Correct 90 ms 84444 KB Output is correct
12 Correct 90 ms 84440 KB Output is correct
13 Correct 89 ms 84472 KB Output is correct
14 Correct 89 ms 84472 KB Output is correct
15 Correct 85 ms 84452 KB Output is correct
16 Correct 88 ms 84472 KB Output is correct
17 Correct 83 ms 84472 KB Output is correct
18 Correct 83 ms 84472 KB Output is correct
19 Correct 90 ms 84476 KB Output is correct
20 Correct 84 ms 84444 KB Output is correct
21 Incorrect 85 ms 84472 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 84472 KB Output is correct
2 Correct 90 ms 84476 KB Output is correct
3 Correct 90 ms 84472 KB Output is correct
4 Correct 89 ms 84472 KB Output is correct
5 Correct 89 ms 84472 KB Output is correct
6 Correct 90 ms 84460 KB Output is correct
7 Correct 88 ms 84600 KB Output is correct
8 Correct 89 ms 84444 KB Output is correct
9 Correct 90 ms 84472 KB Output is correct
10 Correct 90 ms 84476 KB Output is correct
11 Correct 90 ms 84444 KB Output is correct
12 Correct 90 ms 84440 KB Output is correct
13 Correct 89 ms 84472 KB Output is correct
14 Correct 89 ms 84472 KB Output is correct
15 Correct 85 ms 84452 KB Output is correct
16 Correct 88 ms 84472 KB Output is correct
17 Correct 83 ms 84472 KB Output is correct
18 Correct 83 ms 84472 KB Output is correct
19 Correct 90 ms 84476 KB Output is correct
20 Correct 84 ms 84444 KB Output is correct
21 Incorrect 85 ms 84472 KB Output isn't correct
22 Halted 0 ms 0 KB -