oj.uz

Submission #1004656

# Submission time Handle Problem Language Result Execution time Memory
1004656 2024-06-21T11:37:56 Z vjudge1 Pastiri (COI20_pastiri) C++14
100 / 100
 635 ms 87704 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 ancestor ){
  pai[cur] = ancestor;
  for( int viz : adj[cur] ) if( viz != ancestor ){ 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( 1, 1 );

  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;
      |                                         ^~~~
pastiri.cpp:61:7: warning: unused variable 'centro' [-Wunused-variable]
   61 |   int centro = get_centro(n);
      |       ^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 81492 KB Output is correct
2 Correct 278 ms 81488 KB Output is correct
3 Correct 279 ms 81492 KB Output is correct
4 Correct 363 ms 87704 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20312 KB Output is correct
2 Correct 10 ms 20316 KB Output is correct
3 Correct 491 ms 58044 KB Output is correct
4 Correct 502 ms 62252 KB Output is correct
5 Correct 427 ms 42320 KB Output is correct
6 Correct 538 ms 46164 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 10 ms 20060 KB Output is correct
3 Correct 9 ms 20276 KB Output is correct
4 Correct 9 ms 20056 KB Output is correct
5 Correct 10 ms 20312 KB Output is correct
6 Correct 9 ms 20056 KB Output is correct
7 Correct 9 ms 20056 KB Output is correct
8 Correct 9 ms 20060 KB Output is correct
9 Correct 9 ms 20060 KB Output is correct
10 Correct 9 ms 20328 KB Output is correct
11 Correct 9 ms 20060 KB Output is correct
12 Correct 8 ms 20052 KB Output is correct
13 Correct 11 ms 20060 KB Output is correct
14 Correct 9 ms 20316 KB Output is correct
15 Correct 10 ms 20236 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 49800 KB Output is correct
2 Correct 502 ms 51740 KB Output is correct
3 Correct 600 ms 55172 KB Output is correct
4 Correct 393 ms 42324 KB Output is correct
5 Correct 421 ms 46416 KB Output is correct
6 Correct 579 ms 65144 KB Output is correct
7 Correct 549 ms 58936 KB Output is correct
8 Correct 561 ms 56972 KB Output is correct
9 Correct 562 ms 42576 KB Output is correct
10 Correct 384 ms 42324 KB Output is correct
11 Correct 547 ms 63200 KB Output is correct
12 Correct 605 ms 70468 KB Output is correct
13 Correct 635 ms 72332 KB Output is correct
14 Correct 551 ms 68132 KB Output is correct
15 Correct 66 ms 24792 KB Output is correct
16 Correct 433 ms 41804 KB Output is correct
17 Correct 439 ms 51824 KB Output is correct
18 Correct 353 ms 38384 KB Output is correct
19 Correct 552 ms 57220 KB Output is correct
20 Correct 521 ms 60744 KB Output is correct
21 Correct 511 ms 51100 KB Output is correct
22 Correct 500 ms 51828 KB Output is correct