oj.uz

Submission #481233

# Submission time Handle Problem Language Result Execution time Memory
481233 2021-10-20T01:42:23 Z Rainbowbunny Pastiri (COI20_pastiri) C++17
100 / 100
 981 ms 130884 KB 
#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);
  	Ans.reserve(MAXN);
  	V.reserve(MAXN);
    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

# Verdict Execution time Memory Grader output
1 Correct 278 ms 130372 KB Output is correct
2 Correct 390 ms 130884 KB Output is correct
3 Correct 420 ms 129992 KB Output is correct
4 Correct 498 ms 125612 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24596 KB Output is correct
2 Correct 18 ms 24524 KB Output is correct
3 Correct 664 ms 99016 KB Output is correct
4 Correct 693 ms 100980 KB Output is correct
5 Correct 859 ms 98848 KB Output is correct
6 Correct 941 ms 101540 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24140 KB Output is correct
2 Correct 15 ms 24140 KB Output is correct
3 Correct 14 ms 24072 KB Output is correct
4 Correct 14 ms 24012 KB Output is correct
5 Correct 15 ms 24136 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 15 ms 24140 KB Output is correct
8 Correct 16 ms 24112 KB Output is correct
9 Correct 15 ms 24140 KB Output is correct
10 Correct 14 ms 24092 KB Output is correct
11 Correct 15 ms 23940 KB Output is correct
12 Correct 14 ms 23964 KB Output is correct
13 Correct 15 ms 24100 KB Output is correct
14 Correct 15 ms 24160 KB Output is correct
15 Correct 16 ms 24036 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 100060 KB Output is correct
2 Correct 794 ms 99084 KB Output is correct
3 Correct 861 ms 95172 KB Output is correct
4 Correct 905 ms 98652 KB Output is correct
5 Correct 671 ms 81728 KB Output is correct
6 Correct 897 ms 97920 KB Output is correct
7 Correct 981 ms 98932 KB Output is correct
8 Correct 981 ms 99456 KB Output is correct
9 Correct 967 ms 99648 KB Output is correct
10 Correct 859 ms 99704 KB Output is correct
11 Correct 640 ms 100848 KB Output is correct
12 Correct 670 ms 99844 KB Output is correct
13 Correct 634 ms 97672 KB Output is correct
14 Correct 549 ms 102764 KB Output is correct
15 Correct 97 ms 36676 KB Output is correct
16 Correct 863 ms 93124 KB Output is correct
17 Correct 718 ms 82888 KB Output is correct
18 Correct 737 ms 86088 KB Output is correct
19 Correct 856 ms 102404 KB Output is correct
20 Correct 940 ms 107268 KB Output is correct
21 Correct 789 ms 99644 KB Output is correct
22 Correct 797 ms 100192 KB Output is correct