Submission #1004021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004021		vjudge1	Pastiri (COI20_pastiri)	C++14	100 / 100	676 ms	72244 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;

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

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