oj.uz

Submission #481057

# Submission time Handle Problem Language Result Execution time Memory
481057 2021-10-19T11:21:45 Z Rainbowbunny Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 136648 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 <= 19; 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 = 19; 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 306 ms 132352 KB Output is correct
2 Correct 434 ms 132708 KB Output is correct
3 Correct 424 ms 136648 KB Output is correct
4 Correct 541 ms 135124 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24524 KB Output is correct
2 Correct 16 ms 24592 KB Output is correct
3 Correct 751 ms 105644 KB Output is correct
4 Correct 728 ms 107468 KB Output is correct
5 Correct 906 ms 105308 KB Output is correct
6 Correct 975 ms 108124 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24140 KB Output is correct
2 Correct 14 ms 24072 KB Output is correct
3 Correct 14 ms 24072 KB Output is correct
4 Correct 16 ms 23984 KB Output is correct
5 Correct 17 ms 24140 KB Output is correct
6 Correct 16 ms 24160 KB Output is correct
7 Correct 16 ms 24076 KB Output is correct
8 Correct 15 ms 24104 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 15 ms 24076 KB Output is correct
11 Correct 14 ms 24060 KB Output is correct
12 Correct 15 ms 23984 KB Output is correct
13 Correct 17 ms 24012 KB Output is correct
14 Correct 17 ms 24204 KB Output is correct
15 Correct 16 ms 24100 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 103132 KB Output is correct
2 Correct 966 ms 105816 KB Output is correct
3 Correct 966 ms 103960 KB Output is correct
4 Correct 976 ms 105288 KB Output is correct
5 Correct 739 ms 88840 KB Output is correct
6 Execution timed out 1014 ms 106672 KB Time limit exceeded
7 Halted 0 ms 0 KB -