oj.uz

Submission #481090

# Submission time Handle Problem Language Result Execution time Memory
481090 2021-10-19T12:48:26 Z atoiz Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 128200 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;
  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 <= 18; i++)
  {
    for (int node = 1; node <= n; node++)
    {
      up[i][node] = up[i - 1][up[i - 1][node]];
    }
  }
  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 229 ms 127556 KB Output is correct
2 Correct 367 ms 128200 KB Output is correct
3 Correct 338 ms 128116 KB Output is correct
4 Correct 466 ms 124552 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24612 KB Output is correct
2 Correct 17 ms 24636 KB Output is correct
3 Correct 599 ms 96992 KB Output is correct
4 Correct 590 ms 98996 KB Output is correct
5 Correct 727 ms 96856 KB Output is correct
6 Correct 805 ms 99524 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24164 KB Output is correct
2 Correct 13 ms 24244 KB Output is correct
3 Correct 15 ms 24240 KB Output is correct
4 Correct 15 ms 24204 KB Output is correct
5 Correct 16 ms 24252 KB Output is correct
6 Correct 15 ms 24140 KB Output is correct
7 Correct 15 ms 24180 KB Output is correct
8 Correct 15 ms 24268 KB Output is correct
9 Correct 15 ms 24168 KB Output is correct
10 Correct 16 ms 24212 KB Output is correct
11 Correct 14 ms 24104 KB Output is correct
12 Correct 14 ms 24092 KB Output is correct
13 Correct 15 ms 24232 KB Output is correct
14 Correct 16 ms 24316 KB Output is correct
15 Correct 16 ms 24248 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 97228 KB Output is correct
2 Correct 829 ms 97132 KB Output is correct
3 Execution timed out 1075 ms 94112 KB Time limit exceeded
4 Halted 0 ms 0 KB -