oj.uz

Submission #1004022

# Submission time Handle Problem Language Result Execution time Memory
1004022 2024-06-21T01:09:22 Z vjudge1 Pastiri (COI20_pastiri) C++14
100 / 100
 627 ms 72340 KB 
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl
#define pii pair<int, int>

const int maxn = 5e5 + 10;
vector<int> adj[maxn], dist( maxn, maxn ), grau( maxn ), nivel( maxn ), pai( maxn );
vector<bool> sheep( maxn ), marc( maxn );
set<pii> folhas;


void bfs( vector<int>& sources ){
  queue<int> fila;
  for( int x : sources ){ fila.push(x); dist[x] = 0; }
  while( !fila.empty() ){
    int cur = fila.front(); fila.pop();
    for( int viz : adj[cur] ) if( dist[viz] > dist[cur] + 1 ){ fila.push(viz); dist[viz] = dist[cur] + 1; }
  }
}

int get_centro( int n ){
  queue<int> fila;
  for( int i = 1; i <= n; i++ ) if( grau[i] == 1 ) fila.push(i);
  while( fila.size() > 1 ){
    int cur = fila.front(); fila.pop();
    for( int viz : adj[cur] ) if( --grau[viz] == 1 ) fila.push(viz);
  }
  for( int i = 1; i <= n; i++ ) grau[i] = adj[i].size();
  return fila.front();
}

void dfsInit( int cur, int last ){
  pai[cur] = last;
  for( int viz : adj[cur] ) if( viz != last ){ nivel[viz] = nivel[cur] + 1; dfsInit( viz, cur ); }
  if( !sheep[cur] ) nivel[cur] = maxn;
  if( grau[cur] == 1 ) folhas.insert({ nivel[cur], cur });
}

int get_pastor( int cur, int pai ){
  for( int viz : adj[cur] ) if( !marc[viz] && viz != pai && dist[viz] > dist[cur] ) return get_pastor( viz, cur );
  return cur;
}

void dfs( int cur ){
  marc[cur] = true;
  for( int viz : adj[cur] ) if( !marc[viz] && dist[viz] < dist[cur] ) dfs( viz );
}

int main(){
  int n, k; cin >> n >> k;
  for( int i = 1; i < n; i++ ){
    int a, b; cin >> a >> b;
    adj[a].push_back(b); grau[a]++;
    adj[b].push_back(a); grau[b]++;
  }
  vector<int> v(k), resp;
  for( int i = 0; i < k; i++ ){ cin >> v[i]; sheep[v[i]] = true; }
  if( n == 1 ){ cout << 1 << endl << 1; return 0; }
  bfs(v);

  int centro = get_centro(n);
  dfsInit( centro, centro );

  while( !folhas.empty() ){
    int cur = prev(folhas.end())->second; folhas.erase(prev(folhas.end()));

    if( !sheep[cur] ) marc[cur] = true;
    if( !marc[cur] ){
      int pastor = get_pastor(cur, cur);
      resp.push_back(pastor);
      dfs(pastor);
    }

    if( --grau[pai[cur]] == 1 ) folhas.insert({ nivel[pai[cur]], pai[cur] });
  }

  cout << resp.size() << endl;
  for( int x : resp ) cout << x << " "; cout << endl;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:78:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |   for( int x : resp ) cout << x << " "; cout << endl;
      |   ^~~
pastiri.cpp:78:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |   for( int x : resp ) cout << x << " "; cout << endl;
      |                                         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 61864 KB Output is correct
2 Correct 251 ms 61748 KB Output is correct
3 Correct 296 ms 61888 KB Output is correct
4 Correct 354 ms 68208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20312 KB Output is correct
2 Correct 10 ms 20316 KB Output is correct
3 Correct 512 ms 57824 KB Output is correct
4 Correct 561 ms 62156 KB Output is correct
5 Correct 387 ms 42320 KB Output is correct
6 Correct 511 ms 44880 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20060 KB Output is correct
2 Correct 8 ms 20060 KB Output is correct
3 Correct 7 ms 20060 KB Output is correct
4 Correct 9 ms 20060 KB Output is correct
5 Correct 8 ms 20204 KB Output is correct
6 Correct 8 ms 20248 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 9 ms 20060 KB Output is correct
9 Correct 8 ms 20316 KB Output is correct
10 Correct 8 ms 20316 KB Output is correct
11 Correct 9 ms 20060 KB Output is correct
12 Correct 8 ms 20060 KB Output is correct
13 Correct 10 ms 20060 KB Output is correct
14 Correct 9 ms 20168 KB Output is correct
15 Correct 9 ms 20060 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 51616 KB Output is correct
2 Correct 548 ms 51492 KB Output is correct
3 Correct 609 ms 55108 KB Output is correct
4 Correct 385 ms 42320 KB Output is correct
5 Correct 431 ms 46316 KB Output is correct
6 Correct 616 ms 63068 KB Output is correct
7 Correct 604 ms 58704 KB Output is correct
8 Correct 568 ms 55748 KB Output is correct
9 Correct 568 ms 42396 KB Output is correct
10 Correct 400 ms 42272 KB Output is correct
11 Correct 545 ms 63312 KB Output is correct
12 Correct 585 ms 70396 KB Output is correct
13 Correct 608 ms 72340 KB Output is correct
14 Correct 542 ms 68004 KB Output is correct
15 Correct 64 ms 24684 KB Output is correct
16 Correct 509 ms 41796 KB Output is correct
17 Correct 488 ms 51652 KB Output is correct
18 Correct 390 ms 38316 KB Output is correct
19 Correct 627 ms 55524 KB Output is correct
20 Correct 572 ms 59724 KB Output is correct
21 Correct 560 ms 51288 KB Output is correct
22 Correct 573 ms 51568 KB Output is correct