제출 #703635

#제출 시각아이디문제언어결과실행 시간메모리
703635Username4132Pastiri (COI20_pastiri)C++14
100 / 100
822 ms113140 KiB
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back

const int MAXN = 500010;
int n, m, dis[MAXN], par[MAXN], dep[MAXN], ord[MAXN], up[21][MAXN];
bool vis[MAXN], del[MAXN], has[MAXN];
vector<int> g[MAXN], ans;
queue<int> Q;

void bfs(){
    while(!Q.empty()){
        int v= Q.front();
        Q.pop();
        for(auto to:g[v]){
            if(vis[to]) continue;
            dis[to]=dis[v]+1;
            vis[to]=true;
            Q.push(to);
        }
    }
}

void dfs(int v, int p){
    par[v]=p;
    for(auto to:g[v]){
        if(to==p) continue;
        dep[to]=dep[v]+1;
        dfs(to, v);
    }
}

void dele(int v, int p){
    del[v]=true;
    for(auto to:g[v]){
        if(to==p) continue;
        if(dis[to]<dis[v] && !del[to]) dele(to, v);
    }
}

void calc(){
    forn(i, n) up[0][i]=par[i];
    forn(i, 20) forn(j, n) up[i+1][j]=up[i][up[i][j]];
}

int main(){
    scanf("%d %d", &n, &m);
    forn(i, n-1){
        int a, b; scanf("%d %d", &a, &b);
        --a, --b;
        g[a].PB(b), g[b].PB(a);
    }

    forn(i, m){
        int a; scanf("%d", &a);
        --a;
        vis[a]=has[a]=true, Q.push(a);
    }

    bfs();
    dfs(0, 0);
    calc();

    forn(i, n) ord[i]=i;
    sort(ord, ord+n, [](int a, int b){
        return dep[a]>dep[b];
    });

    forn(index, n){
        int v = ord[index];
        if(!has[v] || del[v]) continue;
        int cur=v;
        dforn(i, 21) if(dis[up[i][cur]]==dis[cur]+(1<<i)) cur = up[i][cur];
        ans.PB(cur);
        dele(cur, cur);
    }

    printf("%d\n", (int)ans.size());
    for(auto el:ans) printf("%d ", el+1);
}

컴파일 시 표준 에러 (stderr) 메시지

pastiri.cpp: In function 'int main()':
pastiri.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:61:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         int a; scanf("%d", &a);
      |                ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...