oj.uz

Submission #877272

# Submission time Handle Problem Language Result Execution time Memory
877272 2023-11-23T05:17:01 Z socpite Pastiri (COI20_pastiri) C++14
100 / 100
 482 ms 74784 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;

int d[maxn];

int n, k;
vector<int> g[maxn];

int mark[maxn];
int dep[maxn];
int par[maxn];
int used[maxn];
int X[maxn];

bool cmp(int a, int b)
{
    return dep[a] > dep[b];
}

void dfs(int x, int p)
{
    dep[x] = dep[p] + 1;
    par[x] = p;
    for (auto v : g[x])
    {
        if (v == p)
            continue;
        dfs(v, x);
    }
}

void bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        d[i] = -1;
    }
    for (int i = 0; i < k; i++)
    {
        d[X[i]] = 0;
        q.push(X[i]);
    }
    while (!q.empty())
    {
        auto x = q.front();
        // cout << x << " " << d[x] << endl;
        q.pop();
        for (auto v : g[x])
        {
            if (d[v] != -1)
                continue;
            d[v] = d[x] + 1;
            q.push(v);
        }
    }
}

void clear(int x)
{
    mark[x] = 1;
    for (auto v : g[x])
    {
        if (mark[v] || d[v] != d[x] - 1)
            continue;
        clear(v);
    }
}

vector<int> ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < k; i++)
        cin >> X[i];
    dfs(1, 0);
    bfs();
    sort(X, X + k, cmp);
    for (int i = 0; i < k; i++)
    {
        if (mark[X[i]])
            continue;
        int crr = X[i];
        while (par[crr] && d[par[crr]] == d[crr]+1)
            crr = par[crr];
        ans.push_back(crr);
        clear(crr);
    }
    cout << ans.size() << "\n";
    for (auto v : ans)
        cout << v << " ";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 60932 KB Output is correct
2 Correct 135 ms 62552 KB Output is correct
3 Correct 141 ms 67664 KB Output is correct
4 Correct 211 ms 74784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16996 KB Output is correct
2 Correct 4 ms 17000 KB Output is correct
3 Correct 294 ms 44380 KB Output is correct
4 Correct 239 ms 46684 KB Output is correct
5 Correct 338 ms 43968 KB Output is correct
6 Correct 454 ms 45888 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16956 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 3 ms 16896 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16728 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 38016 KB Output is correct
2 Correct 380 ms 44712 KB Output is correct
3 Correct 436 ms 49456 KB Output is correct
4 Correct 362 ms 44000 KB Output is correct
5 Correct 275 ms 44620 KB Output is correct
6 Correct 357 ms 53080 KB Output is correct
7 Correct 393 ms 51536 KB Output is correct
8 Correct 405 ms 51336 KB Output is correct
9 Correct 482 ms 44116 KB Output is correct
10 Correct 367 ms 43976 KB Output is correct
11 Correct 260 ms 45908 KB Output is correct
12 Correct 215 ms 51280 KB Output is correct
13 Correct 241 ms 52808 KB Output is correct
14 Correct 208 ms 47952 KB Output is correct
15 Correct 34 ms 21216 KB Output is correct
16 Correct 465 ms 42272 KB Output is correct
17 Correct 275 ms 45208 KB Output is correct
18 Correct 383 ms 39140 KB Output is correct
19 Correct 412 ms 50596 KB Output is correct
20 Correct 448 ms 53348 KB Output is correct
21 Correct 334 ms 44072 KB Output is correct
22 Correct 359 ms 44616 KB Output is correct