oj.uz

Submission #1093139

# Submission time Handle Problem Language Result Execution time Memory
1093139 2024-09-26T02:54:22 Z ShadowShark Pastiri (COI20_pastiri) C++17
100 / 100
 728 ms 200508 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e5 + 5;
int depth[maxN], dis[maxN], par[20][maxN], done[maxN];
bool visited[maxN];
vector<int> adj[maxN], save, order[maxN];

void dfs(int u, int pre) {
    for (auto v: adj[u]) {
        if (v == pre) continue;
        depth[v] = depth[u] + 1;
        par[0][v] = u;
        dfs(v, u);
    }
}

void bfs() {
    queue<int> Q;
    for (auto it: save) {
        visited[it] = true;
        Q.push(it);
    }

    while (Q.size() > 0) {
        int u = Q.front(); Q.pop();
        for (auto v: adj[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            dis[v] = dis[u] + 1;
            Q.push(v);
        }
    }
}

bool cmp(int u, int v) {
    return dis[u] < dis[v];
}
map<int, int> rem[maxN];

void mark_done(int u) {
    done[u] = 1;
    int st = rem[u][dis[u] - 1] - 1;
    if (st == -1) return ;
    while (st < adj[u].size() && dis[adj[u][st]] + 1 == dis[u]) {
        if (!done[adj[u][st]]) mark_done(adj[u][st]);
        st++;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;
    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);
    }


    depth[1] = 1;
    dfs(1, 1);

    for (int j = 1; j <= 18; j++)
        for (int i = 1; i <= n; i++)
            par[j][i] = par[j - 1][par[j - 1][i]];

    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;

        order[depth[x]].push_back(x);
        save.push_back(x);
    }

    bfs();

    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end(), cmp);
        //for (auto v: adj[i])
            //cout << v << ' ';
        //cout << '\n';
        int pre = -1;
        for (int id = 0; id < adj[i].size(); id++)
            if (dis[adj[i][id]] != pre) {
                pre = dis[adj[i][id]];
                rem[i][pre] = id + 1;
            }
    }

    vector<int> ans;
    for (int dpth = n; dpth >= 1; dpth--) {
        for (auto it: order[dpth]) {
            int u = it;
            if (done[u]) continue;

            int x = u;
            for (int j = 18; j >= 0; j--) {
                int v = par[j][x];
                if (v != 0 && depth[u] - depth[v] == dis[v]) x = v;
            }

            mark_done(x);

            //cout << u << ' ' << x << '\n';
           // for (int i = 1; i <= n; i++)
                //cout << done[i] << ' ';
            //cout << '\n';

            ans.push_back(x);
        }
    }

    cout << ans.size() << '\n';
    for (auto v: ans)
        cout << v << ' ';

    return 0;
}

Compilation message

pastiri.cpp: In function 'void mark_done(int)':
pastiri.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (st < adj[u].size() && dis[adj[u][st]] + 1 == dis[u]) {
      |            ~~~^~~~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:89:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int id = 0; id < adj[i].size(); id++)
      |                          ~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 183124 KB Output is correct
2 Correct 228 ms 184448 KB Output is correct
3 Correct 218 ms 184656 KB Output is correct
4 Correct 390 ms 200508 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 48476 KB Output is correct
2 Correct 22 ms 48472 KB Output is correct
3 Correct 290 ms 136348 KB Output is correct
4 Correct 311 ms 136908 KB Output is correct
5 Correct 403 ms 153412 KB Output is correct
6 Correct 545 ms 156244 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47964 KB Output is correct
2 Correct 20 ms 48216 KB Output is correct
3 Correct 19 ms 47960 KB Output is correct
4 Correct 19 ms 47872 KB Output is correct
5 Correct 19 ms 47960 KB Output is correct
6 Correct 19 ms 47964 KB Output is correct
7 Correct 19 ms 47964 KB Output is correct
8 Correct 19 ms 47964 KB Output is correct
9 Correct 19 ms 47964 KB Output is correct
10 Correct 20 ms 47708 KB Output is correct
11 Correct 19 ms 47708 KB Output is correct
12 Correct 18 ms 47708 KB Output is correct
13 Correct 18 ms 47920 KB Output is correct
14 Correct 18 ms 47960 KB Output is correct
15 Correct 18 ms 47964 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 145940 KB Output is correct
2 Correct 441 ms 145776 KB Output is correct
3 Correct 557 ms 146264 KB Output is correct
4 Correct 399 ms 153420 KB Output is correct
5 Correct 466 ms 130696 KB Output is correct
6 Correct 604 ms 160400 KB Output is correct
7 Correct 728 ms 155092 KB Output is correct
8 Correct 645 ms 154820 KB Output is correct
9 Correct 624 ms 153428 KB Output is correct
10 Correct 400 ms 153528 KB Output is correct
11 Correct 296 ms 135776 KB Output is correct
12 Correct 380 ms 143808 KB Output is correct
13 Correct 443 ms 150000 KB Output is correct
14 Correct 296 ms 133408 KB Output is correct
15 Correct 72 ms 65364 KB Output is correct
16 Correct 539 ms 144724 KB Output is correct
17 Correct 475 ms 131284 KB Output is correct
18 Correct 434 ms 134396 KB Output is correct
19 Correct 493 ms 150996 KB Output is correct
20 Correct 516 ms 156104 KB Output is correct
21 Correct 332 ms 144980 KB Output is correct
22 Correct 362 ms 145624 KB Output is correct