oj.uz

답안 #481101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481101 2021-10-19T13:04:10 Z atoiz Pastiri (COI20_pastiri) C++14
100 / 100
 988 ms 129972 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);
    }
}
 
struct __init__
{
  __init__()
  {
    Ans.reserve(MAXN);
    V.reserve(MAXN);
  }
} __init_obj__;

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 267 ms 129584 KB Output is correct
2 Correct 421 ms 129920 KB Output is correct
3 Correct 415 ms 129972 KB Output is correct
4 Correct 521 ms 125520 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24524 KB Output is correct
2 Correct 18 ms 24524 KB Output is correct
3 Correct 670 ms 98964 KB Output is correct
4 Correct 682 ms 100924 KB Output is correct
5 Correct 883 ms 98652 KB Output is correct
6 Correct 910 ms 101512 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24140 KB Output is correct
2 Correct 15 ms 24164 KB Output is correct
3 Correct 17 ms 24140 KB Output is correct
4 Correct 15 ms 24088 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 16 ms 24156 KB Output is correct
7 Correct 14 ms 24140 KB Output is correct
8 Correct 18 ms 24064 KB Output is correct
9 Correct 16 ms 24152 KB Output is correct
10 Correct 17 ms 24140 KB Output is correct
11 Correct 16 ms 24028 KB Output is correct
12 Correct 15 ms 23884 KB Output is correct
13 Correct 15 ms 24012 KB Output is correct
14 Correct 14 ms 24140 KB Output is correct
15 Correct 15 ms 24160 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 813 ms 99164 KB Output is correct
2 Correct 783 ms 99112 KB Output is correct
3 Correct 875 ms 95300 KB Output is correct
4 Correct 954 ms 98604 KB Output is correct
5 Correct 669 ms 81960 KB Output is correct
6 Correct 900 ms 98012 KB Output is correct
7 Correct 988 ms 97932 KB Output is correct
8 Correct 982 ms 98640 KB Output is correct
9 Correct 946 ms 98720 KB Output is correct
10 Correct 895 ms 98660 KB Output is correct
11 Correct 665 ms 99948 KB Output is correct
12 Correct 659 ms 98980 KB Output is correct
13 Correct 678 ms 96740 KB Output is correct
14 Correct 562 ms 101976 KB Output is correct
15 Correct 102 ms 35908 KB Output is correct
16 Correct 898 ms 92360 KB Output is correct
17 Correct 719 ms 82192 KB Output is correct
18 Correct 757 ms 85240 KB Output is correct
19 Correct 934 ms 101392 KB Output is correct
20 Correct 963 ms 106368 KB Output is correct
21 Correct 772 ms 98696 KB Output is correct
22 Correct 818 ms 99528 KB Output is correct