oj.uz

Submission #703634

# Submission time Handle Problem Language Result Execution time Memory
703634 2023-02-28T01:08:55 Z Username4132 Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 113020 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]) 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 199 ms 108496 KB Output is correct
2 Correct 238 ms 109336 KB Output is correct
3 Correct 245 ms 109280 KB Output is correct
4 Correct 318 ms 113020 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 12920 KB Output is correct
3 Correct 451 ms 77976 KB Output is correct
4 Correct 475 ms 80332 KB Output is correct
5 Correct 577 ms 77740 KB Output is correct
6 Correct 997 ms 80540 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 9 ms 12500 KB Output is correct
3 Correct 8 ms 12500 KB Output is correct
4 Correct 7 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 8 ms 12496 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 12524 KB Output is correct
11 Correct 9 ms 12372 KB Output is correct
12 Correct 7 ms 12372 KB Output is correct
13 Correct 9 ms 12432 KB Output is correct
14 Correct 7 ms 12500 KB Output is correct
15 Correct 8 ms 12500 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 78968 KB Output is correct
2 Correct 558 ms 78940 KB Output is correct
3 Correct 722 ms 80224 KB Output is correct
4 Correct 545 ms 77992 KB Output is correct
5 Correct 478 ms 67372 KB Output is correct
6 Correct 647 ms 83748 KB Output is correct
7 Correct 866 ms 82612 KB Output is correct
8 Correct 842 ms 82536 KB Output is correct
9 Correct 717 ms 78104 KB Output is correct
10 Correct 560 ms 77904 KB Output is correct
11 Correct 398 ms 80032 KB Output is correct
12 Correct 374 ms 81704 KB Output is correct
13 Correct 393 ms 82740 KB Output is correct
14 Correct 308 ms 81732 KB Output is correct
15 Correct 69 ms 23244 KB Output is correct
16 Execution timed out 1095 ms 72772 KB Time limit exceeded
17 Halted 0 ms 0 KB -