Submission #703634

#	Time	Username	Problem	Language	Result	Execution time	Memory
703634		Username4132	Pastiri (COI20_pastiri)	C++14	49 / 100	1095 ms	113020 KiB

pastiri

#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]) 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);
}

Compilation message (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);
      |                ~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51