oj.uz

Submission #321217

# Submission time Handle Problem Language Result Execution time Memory
321217 2020-11-11T14:51:27 Z georgerapeanu Pastiri (COI20_pastiri) C++11
100 / 100
 805 ms 80720 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 500005;

int n,k;
vector<int> graph[NMAX + 5];
queue<int> q;

int dist[NMAX + 5];

int viz[NMAX + 5];
int highest[NMAX + 5];
int lvl[NMAX + 5];

void predfs(int nod,int tata,int mx,int bst){
    lvl[nod] = 1 + lvl[tata];

    if(mx < lvl[nod] + dist[nod]){
        mx = lvl[nod] + dist[nod];
        bst = nod;
    }

    highest[nod] = bst;

    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }
        predfs(it,nod,mx,bst);
    }
}

void dfs_cover(int nod){
    viz[nod] = true;

    for(auto it:graph[nod]){
        if(viz[it] == 0 && dist[nod] == 1 + dist[it]){
            dfs_cover(it);
        }
    }
}


int main(){

    scanf("%d %d",&n,&k);

    for(int i = 1;i < n;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> sheeps;

    for(int i = 1;i <= k;i++){
        int nod;
        scanf("%d",&nod);
        q.push(nod);
        dist[nod] = 1;
        sheeps.push_back(nod);
    }

    while(q.empty() == false){
        int nod = q.front();
        q.pop();

        for(auto it:graph[nod]){
            if(dist[it] == 0){
                dist[it] = dist[nod] + 1;
                q.push(it);
            }
        }
    }

    predfs(1,0,-1,-1);

    sort(sheeps.begin(),sheeps.end(),[&](int a,int b){return lvl[a] > lvl[b];});

    vector<int> ans;

    for(auto it:sheeps){
        if(viz[it] == 0){
            dfs_cover(highest[it]);
            ans.push_back(highest[it]);
        }
    }

    sort(ans.begin(),ans.end());

    printf("%d\n",(int)ans.size());

    for(auto it:ans){
        printf("%d ",it);
    }

    return 0;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
pastiri.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
pastiri.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |         scanf("%d",&nod);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 71908 KB Output is correct
2 Correct 260 ms 73316 KB Output is correct
3 Correct 259 ms 73316 KB Output is correct
4 Correct 373 ms 80720 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12396 KB Output is correct
2 Correct 12 ms 12396 KB Output is correct
3 Correct 518 ms 41444 KB Output is correct
4 Correct 521 ms 43876 KB Output is correct
5 Correct 662 ms 42212 KB Output is correct
6 Correct 805 ms 45156 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 9 ms 12268 KB Output is correct
3 Correct 10 ms 12288 KB Output is correct
4 Correct 10 ms 12140 KB Output is correct
5 Correct 9 ms 12268 KB Output is correct
6 Correct 10 ms 12268 KB Output is correct
7 Correct 10 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12268 KB Output is correct
10 Correct 9 ms 12268 KB Output is correct
11 Correct 9 ms 12140 KB Output is correct
12 Correct 8 ms 12140 KB Output is correct
13 Correct 9 ms 12268 KB Output is correct
14 Correct 9 ms 12268 KB Output is correct
15 Correct 10 ms 12268 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 43236 KB Output is correct
2 Correct 626 ms 43236 KB Output is correct
3 Correct 704 ms 46676 KB Output is correct
4 Correct 630 ms 42340 KB Output is correct
5 Correct 530 ms 40660 KB Output is correct
6 Correct 702 ms 51408 KB Output is correct
7 Correct 739 ms 49244 KB Output is correct
8 Correct 752 ms 48752 KB Output is correct
9 Correct 794 ms 42476 KB Output is correct
10 Correct 661 ms 42428 KB Output is correct
11 Correct 499 ms 44260 KB Output is correct
12 Correct 466 ms 48212 KB Output is correct
13 Correct 532 ms 50132 KB Output is correct
14 Correct 448 ms 45960 KB Output is correct
15 Correct 76 ms 17300 KB Output is correct
16 Correct 705 ms 40184 KB Output is correct
17 Correct 494 ms 41032 KB Output is correct
18 Correct 627 ms 36836 KB Output is correct
19 Correct 654 ms 48140 KB Output is correct
20 Correct 675 ms 51680 KB Output is correct
21 Correct 590 ms 42328 KB Output is correct
22 Correct 604 ms 43104 KB Output is correct