oj.uz

Submission #703633

# Submission time Handle Problem Language Result Execution time Memory
703633 2023-02-28T01:01:06 Z Username4132 Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 80548 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 PB push_back

const int MAXN = 500010;
int n, m, dis[MAXN], par[MAXN], dep[MAXN], ord[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);
    }
}

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);

    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;
        while(dis[cur]<dis[par[cur]]) cur = par[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:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:55:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         int a; scanf("%d", &a);
      |                ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 73948 KB Output is correct
2 Correct 227 ms 74884 KB Output is correct
3 Correct 221 ms 74876 KB Output is correct
4 Correct 270 ms 80548 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 9 ms 12292 KB Output is correct
3 Correct 439 ms 43564 KB Output is correct
4 Correct 411 ms 45948 KB Output is correct
5 Correct 537 ms 43264 KB Output is correct
6 Correct 993 ms 46032 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12164 KB Output is correct
3 Correct 8 ms 12216 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12188 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12188 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 10 ms 12116 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 7 ms 12116 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 44596 KB Output is correct
2 Correct 511 ms 44404 KB Output is correct
3 Correct 520 ms 47180 KB Output is correct
4 Correct 560 ms 43696 KB Output is correct
5 Correct 425 ms 41032 KB Output is correct
6 Correct 563 ms 51352 KB Output is correct
7 Correct 598 ms 49668 KB Output is correct
8 Correct 643 ms 49312 KB Output is correct
9 Correct 701 ms 43764 KB Output is correct
10 Correct 552 ms 43420 KB Output is correct
11 Correct 369 ms 45592 KB Output is correct
12 Correct 319 ms 48576 KB Output is correct
13 Correct 359 ms 50212 KB Output is correct
14 Correct 295 ms 47168 KB Output is correct
15 Correct 51 ms 17384 KB Output is correct
16 Execution timed out 1091 ms 41236 KB Time limit exceeded
17 Halted 0 ms 0 KB -