Submission #1096162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096162		LinhLewLew	Pastiri (COI20_pastiri)	C++17	100 / 100	524 ms	123996 KiB

pastiri

// PhuThuyRuntime <3
// A secret makes a woman woman

#include <bits/stdc++.h>

using namespace std;

#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define bs binary_search
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) ((1 << j) ^ i)
#define onbit(i, j) ((1 << j) | i)
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int n, k, c[5 * N];
vi adj[5 * N];
void inp(){
     cin >> n >> k;
     fo(i, 1, n - 1){
          int u, v; cin >> u >> v;
          adj[u].eb(v);
          adj[v].eb(u);
     }
     fo(i, 1, k) cin >> c[i];
}
bool visited[5 * N];
int dis[5 * N];
void bfs() {
    queue<int> Q;
    fo(i, 1, k){
        visited[c[i]] = true;
        Q.push(c[i]);
    }

    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);
        }
    }
}
int dep[5 * N], up[5 * N][20];
void dfs(int u, int fa){
     for(auto v : adj[u]){
          if(v == fa) continue;
          dep[v] = dep[u] + 1;
          dfs(v, u);
          up[v][0] = u;
     }
}
bool cmp(int a, int b){
     return dep[a] > dep[b];
}
bool done[5 * N];
void mark(int u){
     done[u] = 1;
     for(auto v : adj[u]){
          if(done[v]) continue;
          if(dis[v] + 1 != dis[u]) continue;
          mark(v);
     }
}
void sol(){
     dfs(1, 0);
     bfs();
     fo(j, 1, 19){
          fo(i, 1, n) up[i][j] = up[up[i][j - 1]][j - 1];
     }
     sort(c + 1, c + k + 1, cmp);
     vi ans;
     fo(i, 1, k){
          int u = c[i];
          if(done[u]) continue;
          int x = u;
          foi(j, 19, 0){
               int v = up[x][j];
               if(v != 0 && dep[u] - dep[v] == dis[v]) x = v;
          }
          mark(x);
          ans.eb(x);
     }
     sort(ans.begin(), ans.end());
     cout << ans.size() << '\n';
     for (auto v: ans) if(v == ans.back()) cout << v; else cout << v << ' ';
}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     inp();
     sol();
     return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51