oj.uz

Submission #1003988

# Submission time Handle Problem Language Result Execution time Memory
1003988 2024-06-20T21:14:34 Z vjudge1 Pastiri (COI20_pastiri) C++17
0 / 100
 466 ms 140820 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 265 ms 140516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 76628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 76116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 466 ms 140820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -