oj.uz

Submission #877270

# Submission time Handle Problem Language Result Execution time Memory
877270 2023-11-23T05:14:26 Z CDuong Pastiri (COI20_pastiri) C++17
100 / 100
 480 ms 72072 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname "SHEEP"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 5e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

int n, k;
int dis[mxN], par[mxN], dep[mxN];
bool vis[mxN], visbfs[mxN];
vector<int> G[mxN], res, cand;

void dfs(int v, int p) {
    par[v] = p;
    dep[v] = dep[p] + 1;

    for (int u : G[v]) {
        if (u == p) continue;
        dfs(u, v);
    }
}

void bfs(int v, int len) {
    // vector<int> reset;
    queue<pair<int, int>> q;
    q.emplace(v, 0); visbfs[v] = true;
    while (not q.empty()) {
        int v = q.front().ff, cdis = q.front().ss; q.pop();
        // reset.emplace_back(v);
        if (cdis < len) {
            for (int u : G[v]) if (!visbfs[u] && dis[v] == dis[u] + 1) {
                q.emplace(u, cdis + 1);
                visbfs[u] = true;
            }
        }
        else {
            vis[v] = false;
        }
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    fill(dis + 1, dis + n + 1, -1);
    queue<int> q;
    for (int i = 1; i <= k; ++i) {
        int v; cin >> v;
        vis[v] = true;
        q.emplace(v); dis[v] = 0;
        cand.emplace_back(v);
    }
    while (not q.empty()) {
        int v = q.front(); q.pop();
        for (int u : G[v]) {
            if (dis[u] == -1) {
                dis[u] = dis[v] + 1;
                q.emplace(u);
            }
        }
    }

    dfs(1, 0);

    sort(all(cand), [&](int x, int y) {
        return dep[x] > dep[y];
    });
    for (int v : cand) if (vis[v]) {
        // cout << v << endl;
        int cur = 0;
        while (v != 1 && dis[par[v]] == cur + 1) {
            ++cur, v = par[v];
        }
        // cout << "chosen: " << v << " " << endl;
        res.emplace_back(v);
        bfs(v, dis[v]);
    }
    cout << isz(res) << "\n";
    for (int v : res) cout << v << " ";
    cout << "\n";
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 57744 KB Output is correct
2 Correct 145 ms 59908 KB Output is correct
3 Correct 144 ms 64792 KB Output is correct
4 Correct 225 ms 72072 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 253 ms 41812 KB Output is correct
4 Correct 243 ms 44168 KB Output is correct
5 Correct 347 ms 41268 KB Output is correct
6 Correct 425 ms 43432 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14936 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14964 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 4 ms 14940 KB Output is correct
15 Correct 4 ms 14940 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 35496 KB Output is correct
2 Correct 327 ms 42080 KB Output is correct
3 Correct 368 ms 45736 KB Output is correct
4 Correct 376 ms 41108 KB Output is correct
5 Correct 287 ms 40720 KB Output is correct
6 Correct 430 ms 49512 KB Output is correct
7 Correct 419 ms 47996 KB Output is correct
8 Correct 436 ms 47300 KB Output is correct
9 Correct 480 ms 41300 KB Output is correct
10 Correct 340 ms 41356 KB Output is correct
11 Correct 247 ms 43344 KB Output is correct
12 Correct 230 ms 47456 KB Output is correct
13 Correct 247 ms 49184 KB Output is correct
14 Correct 243 ms 44696 KB Output is correct
15 Correct 30 ms 19416 KB Output is correct
16 Correct 409 ms 39680 KB Output is correct
17 Correct 288 ms 41168 KB Output is correct
18 Correct 314 ms 36688 KB Output is correct
19 Correct 378 ms 46040 KB Output is correct
20 Correct 369 ms 48844 KB Output is correct
21 Correct 330 ms 41496 KB Output is correct
22 Correct 307 ms 41812 KB Output is correct