oj.uz

Submission #481088

# Submission time Handle Problem Language Result Execution time Memory
481088 2021-10-19T12:46:43 Z atoiz Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 128012 KB 
// https://oj.uz/submission/481066

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;
const int INF = 1e9;

int n, k, tim;
int H[MAXN], d[MAXN], a[MAXN];
int up[20][MAXN], cnt[MAXN];
bool Vis[MAXN];
vector <int> Ans, V;
vector <int> NAdj[MAXN];
vector <int> Adj[MAXN];

void DFS(int node, int p = 1)
{
  up[0][node] = p;
  for(int i = 1; i <= 18; i++)
  {
    up[i][node] = up[i - 1][up[i - 1][node]];
  }
  tim++;
  for(auto x : Adj[node])
  {
    if(x == p)
    {
      continue;
    }
    H[x] = H[node] + 1;
    DFS(x, node);
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for(int i = 1; i < n; i++)
  {
    int u, v;
    cin >> u >> v;
    Adj[u].push_back(v);
    Adj[v].push_back(u);
  }
  DFS(1);
  for(int i = 1; i <= n; i++)
  {
    d[i] = -1;
  }
  queue <int> BFS;
  for(int i = 1; i <= k; i++)
  {
    cin >> a[i];
    d[a[i]] = 0;
    BFS.push(a[i]);
    V.push_back(a[i]);
  }
  while(BFS.empty() == false)
  {
    int node = BFS.front();
    BFS.pop();
    for(auto x : Adj[node])
    {
      if(d[x] == -1)
      {
        d[x] = d[node] + 1;
        BFS.push(x);
      }
      if(d[x] == d[node] + 1)
      {
        NAdj[x].push_back(node);
      }
    }
  }
  sort(V.begin(), V.end(), [&](int x, int y)
       {
         return H[x] > H[y];
       });
  for(auto x : V)
  {
    if(Vis[x])
    {
      continue;
    }
    int cur = x;
    for(int i = 18; i >= 0; i--)
    {
      int nx = up[i][cur];
      if(H[x] - H[nx] <= d[nx])
      {
        cur = nx;
      }
    }
    if(Vis[cur])
    {
      continue;
    }
    Ans.push_back(cur);
    queue <int> q;
    Vis[cur] = true;
    q.push(cur);
    while(q.empty() == false)
    {
      int node = q.front();
      q.pop();
      for(auto y : NAdj[node])
      {
        if(!Vis[y])
        {
          Vis[y] = true;
          q.push(y);
        }
      }
    }
  }
  cout << Ans.size() << '\n';
  for(auto x : Ans)
  {
    cout << x << ' ';
  }
  cout << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 127560 KB Output is correct
2 Correct 349 ms 127940 KB Output is correct
3 Correct 376 ms 128012 KB Output is correct
4 Correct 502 ms 124464 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24688 KB Output is correct
2 Correct 18 ms 24652 KB Output is correct
3 Correct 739 ms 97136 KB Output is correct
4 Correct 712 ms 99000 KB Output is correct
5 Correct 807 ms 96764 KB Output is correct
6 Correct 908 ms 99528 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24196 KB Output is correct
2 Correct 14 ms 24264 KB Output is correct
3 Correct 19 ms 24140 KB Output is correct
4 Correct 14 ms 24200 KB Output is correct
5 Correct 16 ms 24256 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 17 ms 24240 KB Output is correct
8 Correct 15 ms 24268 KB Output is correct
9 Correct 14 ms 24268 KB Output is correct
10 Correct 14 ms 24268 KB Output is correct
11 Correct 15 ms 24140 KB Output is correct
12 Correct 13 ms 24016 KB Output is correct
13 Correct 16 ms 24164 KB Output is correct
14 Correct 14 ms 24268 KB Output is correct
15 Correct 14 ms 24172 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 97416 KB Output is correct
2 Correct 967 ms 97092 KB Output is correct
3 Execution timed out 1053 ms 93784 KB Time limit exceeded
4 Halted 0 ms 0 KB -