oj.uz

Submission #703635

# Submission time Handle Problem Language Result Execution time Memory
703635 2023-02-28T01:41:36 Z Username4132 Pastiri (COI20_pastiri) C++14
100 / 100
 822 ms 113140 KB 
#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);
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 108492 KB Output is correct
2 Correct 236 ms 109500 KB Output is correct
3 Correct 243 ms 109324 KB Output is correct
4 Correct 315 ms 113140 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12884 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 409 ms 78020 KB Output is correct
4 Correct 407 ms 80292 KB Output is correct
5 Correct 567 ms 77648 KB Output is correct
6 Correct 687 ms 80556 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Correct 8 ms 12372 KB Output is correct
5 Correct 7 ms 12500 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 7 ms 12436 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 7 ms 12500 KB Output is correct
10 Correct 7 ms 12500 KB Output is correct
11 Correct 7 ms 12372 KB Output is correct
12 Correct 6 ms 12284 KB Output is correct
13 Correct 7 ms 12388 KB Output is correct
14 Correct 7 ms 12500 KB Output is correct
15 Correct 7 ms 12500 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 78980 KB Output is correct
2 Correct 548 ms 78788 KB Output is correct
3 Correct 688 ms 80316 KB Output is correct
4 Correct 559 ms 77992 KB Output is correct
5 Correct 446 ms 67360 KB Output is correct
6 Correct 622 ms 83804 KB Output is correct
7 Correct 822 ms 82832 KB Output is correct
8 Correct 814 ms 82548 KB Output is correct
9 Correct 654 ms 78156 KB Output is correct
10 Correct 559 ms 77900 KB Output is correct
11 Correct 393 ms 79940 KB Output is correct
12 Correct 354 ms 81724 KB Output is correct
13 Correct 385 ms 82648 KB Output is correct
14 Correct 322 ms 81556 KB Output is correct
15 Correct 55 ms 23212 KB Output is correct
16 Correct 605 ms 72848 KB Output is correct
17 Correct 461 ms 74240 KB Output is correct
18 Correct 533 ms 71744 KB Output is correct
19 Correct 671 ms 90480 KB Output is correct
20 Correct 638 ms 93900 KB Output is correct
21 Correct 499 ms 84812 KB Output is correct
22 Correct 517 ms 85436 KB Output is correct