oj.uz

답안 #481085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481085 2021-10-19T12:44:27 Z atoiz Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 130024 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[MAXN][20], 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[node][0] = p;
  for(int i = 1; i <= 18; i++)
  {
    up[node][i] = up[up[node][i - 1]][i - 1];
  }
  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[cur][i];
      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

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 129548 KB Output is correct
2 Correct 380 ms 129832 KB Output is correct
3 Correct 389 ms 130024 KB Output is correct
4 Correct 492 ms 126588 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24524 KB Output is correct
2 Correct 16 ms 24524 KB Output is correct
3 Correct 681 ms 98824 KB Output is correct
4 Correct 644 ms 100852 KB Output is correct
5 Correct 820 ms 98756 KB Output is correct
6 Correct 865 ms 101512 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24140 KB Output is correct
2 Correct 15 ms 24140 KB Output is correct
3 Correct 14 ms 24008 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 15 ms 24056 KB Output is correct
6 Correct 18 ms 24016 KB Output is correct
7 Correct 14 ms 24076 KB Output is correct
8 Correct 13 ms 24136 KB Output is correct
9 Correct 17 ms 24132 KB Output is correct
10 Correct 14 ms 24140 KB Output is correct
11 Correct 16 ms 24040 KB Output is correct
12 Correct 13 ms 23884 KB Output is correct
13 Correct 14 ms 24012 KB Output is correct
14 Correct 14 ms 24140 KB Output is correct
15 Correct 15 ms 24020 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 912 ms 99352 KB Output is correct
2 Correct 880 ms 99064 KB Output is correct
3 Correct 925 ms 95848 KB Output is correct
4 Correct 912 ms 98760 KB Output is correct
5 Correct 672 ms 82232 KB Output is correct
6 Correct 960 ms 98108 KB Output is correct
7 Execution timed out 1057 ms 106520 KB Time limit exceeded
8 Halted 0 ms 0 KB -