oj.uz

Submission #1004021

# Submission time Handle Problem Language Result Execution time Memory
1004021 2024-06-21T01:03:07 Z vjudge1 Pastiri (COI20_pastiri) C++14
100 / 100
 676 ms 72244 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;

queue<int> fila;
void add( int x, int d ){ fila.push(x); dist[x] = d; }

void bfs( vector<int>& sources ){
  for( int x : sources ) add( x, 0 );
  while( !fila.empty() ){
    int cur = fila.front(); fila.pop();
    for( int viz : adj[cur] ) if( dist[viz] > dist[cur] + 1 ) add( 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.empty() ){
    int cur = fila.front(); fila.pop();
    if( grau[cur] == 0 ){
      for( int i = 1; i <= n; i++ ) grau[i] = adj[i].size();
      return cur;
    }
    for( int viz : adj[cur] ) if( --grau[viz] == 1 ) fila.push(viz);
  }
}

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

  }

  sort( resp.begin(), resp.end() );
  cout << resp.size() << endl;
  for( int x : resp ) cout << x << " "; cout << endl;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:84:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   84 |   for( int x : resp ) cout << x << " "; cout << endl;
      |   ^~~
pastiri.cpp:84:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |   for( int x : resp ) cout << x << " "; cout << endl;
      |                                         ^~~~
pastiri.cpp: In function 'int get_centro(int)':
pastiri.cpp:23:14: warning: control reaches end of non-void function [-Wreturn-type]
   23 |   queue<int> fila;
      |              ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 61776 KB Output is correct
2 Correct 245 ms 61740 KB Output is correct
3 Correct 249 ms 61944 KB Output is correct
4 Correct 325 ms 68652 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20316 KB Output is correct
2 Correct 11 ms 20316 KB Output is correct
3 Correct 552 ms 57872 KB Output is correct
4 Correct 542 ms 62288 KB Output is correct
5 Correct 506 ms 42520 KB Output is correct
6 Correct 569 ms 44880 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20060 KB Output is correct
2 Correct 9 ms 20132 KB Output is correct
3 Correct 9 ms 20060 KB Output is correct
4 Correct 9 ms 20236 KB Output is correct
5 Correct 9 ms 20056 KB Output is correct
6 Correct 9 ms 20060 KB Output is correct
7 Correct 9 ms 20060 KB Output is correct
8 Correct 12 ms 20060 KB Output is correct
9 Correct 12 ms 20316 KB Output is correct
10 Correct 10 ms 20312 KB Output is correct
11 Correct 9 ms 20060 KB Output is correct
12 Correct 9 ms 20160 KB Output is correct
13 Correct 9 ms 20060 KB Output is correct
14 Correct 10 ms 20164 KB Output is correct
15 Correct 10 ms 20060 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 51672 KB Output is correct
2 Correct 596 ms 51492 KB Output is correct
3 Correct 647 ms 55236 KB Output is correct
4 Correct 442 ms 42436 KB Output is correct
5 Correct 467 ms 46188 KB Output is correct
6 Correct 591 ms 63128 KB Output is correct
7 Correct 597 ms 58704 KB Output is correct
8 Correct 609 ms 55916 KB Output is correct
9 Correct 556 ms 42576 KB Output is correct
10 Correct 454 ms 42620 KB Output is correct
11 Correct 574 ms 63168 KB Output is correct
12 Correct 676 ms 70468 KB Output is correct
13 Correct 649 ms 72244 KB Output is correct
14 Correct 568 ms 68056 KB Output is correct
15 Correct 68 ms 24748 KB Output is correct
16 Correct 457 ms 41812 KB Output is correct
17 Correct 421 ms 51652 KB Output is correct
18 Correct 392 ms 38424 KB Output is correct
19 Correct 606 ms 55432 KB Output is correct
20 Correct 606 ms 59728 KB Output is correct
21 Correct 535 ms 51192 KB Output is correct
22 Correct 554 ms 51564 KB Output is correct