oj.uz

답안 #163755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163755 2019-11-15T07:34:48 Z georgerapeanu Mergers (JOI19_mergers) C++11
0 / 100
 201 ms 72668 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);
    }
}

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 i = 1;i <= n;i++){
        set<int> tmp;
        for(auto it:graph[i]){
            if(fi_col_root(i) != fi_col_root(it)){
                tmp.insert(fi_col_root(it));
            }
        }
        cnt += (tmp.size() == 1 && seen[state[i]] == false);
        seen[state[i]] = true;
    }

    printf("%d\n",(cnt) / 2);
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:110: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:114: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:120: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

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 61048 KB Output is correct
2 Correct 62 ms 61020 KB Output is correct
3 Incorrect 62 ms 61048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 61048 KB Output is correct
2 Correct 62 ms 61020 KB Output is correct
3 Incorrect 62 ms 61048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 61048 KB Output is correct
2 Correct 62 ms 61020 KB Output is correct
3 Incorrect 62 ms 61048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 72668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 61048 KB Output is correct
2 Correct 62 ms 61020 KB Output is correct
3 Incorrect 62 ms 61048 KB Output isn't correct
4 Halted 0 ms 0 KB -