Submission #1003988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003988		vjudge1	Pastiri (COI20_pastiri)	C++17	0 / 100	466 ms	140820 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], pai( maxn ), dist( maxn, maxn ), marc( maxn ), nivel( maxn ), is_sheep(maxn), adj2[maxn], used( maxn ), grau( maxn );
queue<int> fila;
set<pii> folhas;

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 );
      if( dist[viz] == dist[cur] + 1 ) adj2[viz].push_back(cur);
    }
  }
}

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( !is_sheep[cur] ) nivel[cur] = maxn;
  if( grau[cur] == 1 ) folhas.insert({ nivel[cur], cur });
}

void dfs( int cur ){
  used[cur] = true;
  for( int viz : adj2[cur] ) if( !used[viz] ) dfs( viz );
}

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

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

  bfs(sheep);

  dfsInit( rand(), rand() );

  vector<int> resp;

  while( !folhas.empty() ){
    int cur = prev(folhas.end())->second; folhas.erase(prev(folhas.end()));
    // bug(cur);
    if( !is_sheep[cur] ) used[cur] = true;
    if( used[cur] ) continue;
    int aux = find(cur, cur);
    // bug(aux);
    resp.push_back(aux);
    int next;
    for( int viz : adj[cur] ) if( !used[viz] ) next = viz;
    // bug(next);
    grau[next]--;
    if( grau[next] == 1 ) folhas.insert({ nivel[next], next });

    dfs(aux);
  }

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

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:79:14: warning: 'next' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     grau[next]--;
      |              ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51