oj.uz

Submission #1003859

# Submission time Handle Problem Language Result Execution time Memory
1003859 2024-06-20T19:11:06 Z vjudge1 Pastiri (COI20_pastiri) C++17
0 / 100
 449 ms 65764 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 59100 KB Output is correct
2 Incorrect 358 ms 65764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 20056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20056 KB Output is correct
2 Correct 9 ms 19996 KB Output is correct
3 Correct 9 ms 20060 KB Output is correct
4 Correct 8 ms 20044 KB Output is correct
5 Correct 9 ms 20060 KB Output is correct
6 Correct 13 ms 20060 KB Output is correct
7 Correct 9 ms 20060 KB Output is correct
8 Incorrect 7 ms 20056 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 449 ms 38096 KB Output isn't correct
2 Halted 0 ms 0 KB -