Submission #1004656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004656		vjudge1	Pastiri (COI20_pastiri)	C++14	100 / 100	635 ms	87704 KiB

pastiri

#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 (stderr)

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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51