Submission #1003836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003836		vjudge1	Pastiri (COI20_pastiri)	C++17	0 / 100	358 ms	40272 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 );
queue<int> fila;

void add( int x, int d ){
  fila.push(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 );
  while( !fila.empty() ){
    int cur = fila.front(); fila.pop();
    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;
    }
  }
}

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

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

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