oj.uz

Submission #481066

# Submission time Handle Problem Language Result Execution time Memory
481066 2021-10-19T11:36:49 Z Rainbowbunny Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 130032 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);
    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 261 ms 129492 KB Output is correct
2 Correct 403 ms 130032 KB Output is correct
3 Correct 406 ms 129896 KB Output is correct
4 Correct 515 ms 126500 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 24524 KB Output is correct
3 Correct 715 ms 98956 KB Output is correct
4 Correct 685 ms 100932 KB Output is correct
5 Correct 894 ms 98812 KB Output is correct
6 Correct 938 ms 101488 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24140 KB Output is correct
2 Correct 15 ms 24036 KB Output is correct
3 Correct 16 ms 24176 KB Output is correct
4 Correct 17 ms 23976 KB Output is correct
5 Correct 17 ms 24140 KB Output is correct
6 Correct 16 ms 24048 KB Output is correct
7 Correct 16 ms 24088 KB Output is correct
8 Correct 15 ms 24104 KB Output is correct
9 Correct 17 ms 24092 KB Output is correct
10 Correct 16 ms 24140 KB Output is correct
11 Correct 16 ms 24012 KB Output is correct
12 Correct 16 ms 23968 KB Output is correct
13 Correct 17 ms 24012 KB Output is correct
14 Correct 17 ms 24140 KB Output is correct
15 Correct 16 ms 24140 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 99304 KB Output is correct
2 Correct 928 ms 99140 KB Output is correct
3 Correct 987 ms 95804 KB Output is correct
4 Correct 976 ms 98500 KB Output is correct
5 Correct 752 ms 82232 KB Output is correct
6 Execution timed out 1018 ms 98112 KB Time limit exceeded
7 Halted 0 ms 0 KB -