oj.uz

Submission #481099

# Submission time Handle Problem Language Result Execution time Memory
481099 2021-10-19T12:56:07 Z atoiz Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 130008 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];
queue <int> BFS, q;
 
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(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);
        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 271 ms 129544 KB Output is correct
2 Correct 421 ms 129976 KB Output is correct
3 Correct 406 ms 130008 KB Output is correct
4 Correct 519 ms 126464 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24556 KB Output is correct
2 Correct 18 ms 24524 KB Output is correct
3 Correct 693 ms 98920 KB Output is correct
4 Correct 702 ms 100956 KB Output is correct
5 Correct 882 ms 98580 KB Output is correct
6 Correct 891 ms 101552 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24080 KB Output is correct
2 Correct 16 ms 24152 KB Output is correct
3 Correct 15 ms 24088 KB Output is correct
4 Correct 16 ms 23972 KB Output is correct
5 Correct 16 ms 24156 KB Output is correct
6 Correct 16 ms 24040 KB Output is correct
7 Correct 15 ms 24140 KB Output is correct
8 Correct 17 ms 24140 KB Output is correct
9 Correct 16 ms 24116 KB Output is correct
10 Correct 15 ms 24148 KB Output is correct
11 Correct 15 ms 24036 KB Output is correct
12 Correct 16 ms 24004 KB Output is correct
13 Correct 15 ms 24004 KB Output is correct
14 Correct 15 ms 24140 KB Output is correct
15 Correct 16 ms 24144 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 99224 KB Output is correct
2 Correct 906 ms 99136 KB Output is correct
3 Correct 926 ms 95780 KB Output is correct
4 Correct 954 ms 98664 KB Output is correct
5 Correct 718 ms 82400 KB Output is correct
6 Correct 952 ms 98020 KB Output is correct
7 Execution timed out 1024 ms 98352 KB Time limit exceeded
8 Halted 0 ms 0 KB -