oj.uz

답안 #563772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563772 2022-05-18T06:08:32 Z tqbfjotld Mergers (JOI19_mergers) C++14
0 / 100
 104 ms 54268 KB 
#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;
}

void dfs2(int node, int np, int val){
    val += arr[node];
    for (auto x : adjl[node]){
        if (x==np) continue;
        //printf("node %d, val %d\n",node,val);
        if (val>0){
            mer(node,x);
        }
        dfs2(x,node,val);
    }
}

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,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

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
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 48820 KB Output is correct
2 Correct 104 ms 54268 KB Output is correct
3 Incorrect 21 ms 35924 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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