oj.uz

Submission #481100

# Submission time Handle Problem Language Result Execution time Memory
481100 2021-10-19T13:00:17 Z atoiz Pastiri (COI20_pastiri) C++14
100 / 100
 960 ms 130004 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];
deque <int> BFS, q;
 
struct __init__
{
  __init__()
  {
    Ans.reserve(MAXN);
    V.reserve(MAXN);
  }
} __init_object__;

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;
    }
    for(int i = 1; i <= k; i++)
    {
        cin >> a[i];
        d[a[i]] = 0;
        BFS.push_back(a[i]);
        V.push_back(a[i]);
    }
    while(BFS.empty() == false)
    {
        int node = BFS.front();
        BFS.pop_front();
        for(auto x : Adj[node])
        {
            if(d[x] == -1)
            {
                d[x] = d[node] + 1;
                BFS.push_back(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);
        Vis[cur] = true;
        q.push_back(cur);
        while(q.empty() == false)
        {
            int node = q.front();
            q.pop_front();
            for(auto y : NAdj[node])
            {
                if(!Vis[y])
                {
                    Vis[y] = true;
                    q.push_back(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 277 ms 129476 KB Output is correct
2 Correct 386 ms 129960 KB Output is correct
3 Correct 374 ms 130004 KB Output is correct
4 Correct 475 ms 125420 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24572 KB Output is correct
2 Correct 17 ms 24524 KB Output is correct
3 Correct 694 ms 98960 KB Output is correct
4 Correct 679 ms 101180 KB Output is correct
5 Correct 837 ms 98772 KB Output is correct
6 Correct 910 ms 101636 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24140 KB Output is correct
2 Correct 13 ms 24172 KB Output is correct
3 Correct 14 ms 24140 KB Output is correct
4 Correct 15 ms 24012 KB Output is correct
5 Correct 15 ms 24164 KB Output is correct
6 Correct 18 ms 24120 KB Output is correct
7 Correct 15 ms 24164 KB Output is correct
8 Correct 14 ms 24140 KB Output is correct
9 Correct 14 ms 24140 KB Output is correct
10 Correct 13 ms 24084 KB Output is correct
11 Correct 13 ms 24052 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 14 ms 24012 KB Output is correct
14 Correct 15 ms 24108 KB Output is correct
15 Correct 15 ms 24140 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 99408 KB Output is correct
2 Correct 796 ms 99132 KB Output is correct
3 Correct 891 ms 95332 KB Output is correct
4 Correct 940 ms 98612 KB Output is correct
5 Correct 637 ms 81748 KB Output is correct
6 Correct 897 ms 98072 KB Output is correct
7 Correct 950 ms 97960 KB Output is correct
8 Correct 948 ms 106416 KB Output is correct
9 Correct 957 ms 105452 KB Output is correct
10 Correct 868 ms 105408 KB Output is correct
11 Correct 638 ms 106692 KB Output is correct
12 Correct 662 ms 106948 KB Output is correct
13 Correct 629 ms 105468 KB Output is correct
14 Correct 553 ms 108484 KB Output is correct
15 Correct 96 ms 36932 KB Output is correct
16 Correct 844 ms 98552 KB Output is correct
17 Correct 689 ms 88828 KB Output is correct
18 Correct 731 ms 90580 KB Output is correct
19 Correct 883 ms 108612 KB Output is correct
20 Correct 960 ms 113204 KB Output is correct
21 Correct 764 ms 105484 KB Output is correct
22 Correct 773 ms 106008 KB Output is correct