Submission #1003859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003859		vjudge1	Pastiri (COI20_pastiri)	C++17	0 / 100	449 ms	65764 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl
const int maxn = 5e5 + 10;

vector<int> adj[maxn], dist( maxn, maxn ), pai( maxn ), marc( maxn ), nivel( maxn );
set<pair<int, int>> fila[2];

void add( int x, int d ){
  fila[d%2].insert({ -nivel[x], x });
  dist[x] = d;
}

int find( int a ){ return (( a == pai[a] ) ? a : pai[a] = find(pai[a]) );  }

void bfs( vector<int>& sources ){
  for( int x : sources ) marc[x] = x, add( x, 0 );
  int a = 0, b = 1;
  while( !fila[a].empty() ){
    int cur = fila[a].begin()->second; fila[a].erase(fila[a].begin());
    int cont = 0;
    for( int viz : adj[cur] ){
      if( dist[viz] == dist[cur] - 1 && marc[viz] != 0 && pai[marc[viz]] == marc[viz] ) cont++;
      if( dist[viz] > dist[cur] + 1 ) add( viz, dist[cur] + 1 );
    }
    if( cont ) for( int viz : adj[cur] ) if( dist[viz] == dist[cur] - 1 && marc[viz] && pai[marc[viz]] == marc[viz] ){
      if( cont == 1 ) marc[cur] = marc[viz];
      else pai[marc[viz]] = cur, marc[cur] = cur;
    }
    if( fila[a].empty() ) swap( a, b );
  }
}

void dfs( int cur, int pai ){
  for( int viz : adj[cur] ) if( viz != pai ){ nivel[viz] = nivel[cur] + 1; dfs( viz, cur ); }
}

int main(){
  int n, k; cin >> n >> k;
  pai[n] = n;
  for( int i = 1; i < n; i++ ){
    pai[i] = i;
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  vector<int> sheep(k);
  for( int i = 0; i < k; i++ ) cin >> sheep[i];
  dfs( 1, 1 );

  bfs(sheep);


  set<int> s;
  for( int x : sheep ) s.insert(find(x));

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

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:58:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |   for( int x : s ) cout << x << " "; cout << endl;
      |   ^~~
pastiri.cpp:58:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |   for( int x : s ) cout << x << " "; cout << endl;
      |                                      ^~~~

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