oj.uz

Submission #1096162

# Submission time Handle Problem Language Result Execution time Memory
1096162 2024-10-04T03:11:01 Z LinhLewLew Pastiri (COI20_pastiri) C++17
100 / 100
 524 ms 123996 KB 
// 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 117152 KB Output is correct
2 Correct 202 ms 117584 KB Output is correct
3 Correct 194 ms 117584 KB Output is correct
4 Correct 293 ms 123996 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12892 KB Output is correct
2 Correct 6 ms 12864 KB Output is correct
3 Correct 294 ms 78544 KB Output is correct
4 Correct 244 ms 80844 KB Output is correct
5 Correct 342 ms 78420 KB Output is correct
6 Correct 419 ms 81828 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 5 ms 12380 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct
7 Correct 5 ms 12376 KB Output is correct
8 Correct 6 ms 12380 KB Output is correct
9 Correct 7 ms 12632 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 5 ms 12228 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 6 ms 12584 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 79480 KB Output is correct
2 Correct 346 ms 79700 KB Output is correct
3 Correct 436 ms 82452 KB Output is correct
4 Correct 319 ms 78344 KB Output is correct
5 Correct 324 ms 69572 KB Output is correct
6 Correct 391 ms 87632 KB Output is correct
7 Correct 438 ms 85612 KB Output is correct
8 Correct 452 ms 85212 KB Output is correct
9 Correct 422 ms 78416 KB Output is correct
10 Correct 355 ms 78388 KB Output is correct
11 Correct 296 ms 80352 KB Output is correct
12 Correct 299 ms 84256 KB Output is correct
13 Correct 307 ms 86260 KB Output is correct
14 Correct 275 ms 81612 KB Output is correct
15 Correct 46 ms 23192 KB Output is correct
16 Correct 452 ms 73300 KB Output is correct
17 Correct 356 ms 69888 KB Output is correct
18 Correct 403 ms 66356 KB Output is correct
19 Correct 444 ms 85332 KB Output is correct
20 Correct 524 ms 90164 KB Output is correct
21 Correct 387 ms 78648 KB Output is correct
22 Correct 417 ms 79444 KB Output is correct