Submission #1093139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093139		ShadowShark	Pastiri (COI20_pastiri)	C++17	100 / 100	728 ms	200508 KiB

pastiri

#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 (stderr)

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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51