oj.uz

Submission #877193

# Submission time Handle Problem Language Result Execution time Memory
877193 2023-11-23T03:16:52 Z khueprovip Pastiri (COI20_pastiri) C++17
100 / 100
 486 ms 88344 KB 
#include<bits/stdc++.h>
#define PB push_back
#define maxn 500007
#define bit(x,i) ((x>>i)&1)
#define S second
#define F first
#define MP make_pair
#define epsilon 0.000001

using namespace std;

typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const int inf = 1e18;
const int mod = 1e9+7;
const double PI = acos(-1);

int n,k,dis[maxn],s[maxn],dep[maxn],h[maxn],bio[maxn];
vector<int> adj[maxn];

void readData(){
    cin>>n>>k;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].PB(v);
        adj[v].PB(u);
    }
    for (int i=1;i<=k;i++) cin>>s[i];
}

void dfs_init(int x, int p, int mx, int opt){
    int sum=dep[x]+dis[x];
    if (sum>mx){
        mx=sum;
        opt=x;
    }
    h[x]=opt;
    for (auto v:adj[x]){
        if (v==p) continue;
        dep[v]=dep[x]+1;
        dfs_init(v,x,mx,opt);
    }
}

void bfs(){
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    for (int i=1;i<=k;i++){
        dis[s[i]]=0;
        q.push(s[i]);
    }
    while (q.size()){
        int u=q.front();
        q.pop();
        for (auto v:adj[u]){
            if (dis[v]!=-1) continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
}

bool cmp(int x, int y){
    return dep[x]>dep[y];
}

void dfs_cover(int x){
    bio[x]=1;
    for (auto v:adj[x])
        if (!bio[v]&&dis[x]==dis[v]+1) dfs_cover(v);
}

void solve(){
    bfs();
    dfs_init(1,0,-1,0);
    sort(s+1,s+k+1,cmp);
    vector<int> ans;
    for (int i=1;i<=k;i++){
        if (bio[s[i]]) continue;
        ans.PB(h[s[i]]);
        dfs_cover(h[s[i]]);
    }
    cout<<ans.size()<<"\n";
    for (auto x:ans) cout<<x<<" ";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("SHEEP.inp","r",stdin);
    //freopen(".out","w",stdout);
    readData();
    solve();
    return 0;
}
/*
               _oo0oo_
              o8888888o
              88" . "88
              (| -_- |)
              0\  =  /0
            ___/`---'\___
          .' \\|     |// '.
         / \\|||  :  |||// \
        / _||||| -:- |||||- \
       |   | \\\  -  /// |   |
       | \_|  ''\---/''  |_/ |
       \  .-\__  '-'  ___/-. /
     ___'. .'  /--.--\  `. .'___
  ."" '<  `.___\_<|>_/___.' >' "".
 | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 \  \ `_.   \_ __\ /__ _/   .-` /  /
=====`-.____`.___ \_____/___.-`___.-'=====
               `=---='
*/

Compilation message

pastiri.cpp:14:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const int inf = 1e18;
      |                 ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 83296 KB Output is correct
2 Correct 148 ms 83280 KB Output is correct
3 Correct 171 ms 83516 KB Output is correct
4 Correct 230 ms 88344 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20060 KB Output is correct
2 Correct 5 ms 20072 KB Output is correct
3 Correct 278 ms 44328 KB Output is correct
4 Correct 274 ms 46792 KB Output is correct
5 Correct 341 ms 44192 KB Output is correct
6 Correct 469 ms 47804 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Correct 5 ms 19948 KB Output is correct
4 Correct 5 ms 19804 KB Output is correct
5 Correct 5 ms 19948 KB Output is correct
6 Correct 5 ms 19804 KB Output is correct
7 Correct 4 ms 19800 KB Output is correct
8 Correct 7 ms 19800 KB Output is correct
9 Correct 4 ms 19804 KB Output is correct
10 Correct 4 ms 20040 KB Output is correct
11 Correct 4 ms 19800 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct
13 Correct 6 ms 19804 KB Output is correct
14 Correct 4 ms 20056 KB Output is correct
15 Correct 5 ms 19804 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 45236 KB Output is correct
2 Correct 414 ms 45228 KB Output is correct
3 Correct 404 ms 47228 KB Output is correct
4 Correct 343 ms 44148 KB Output is correct
5 Correct 270 ms 43080 KB Output is correct
6 Correct 416 ms 52052 KB Output is correct
7 Correct 389 ms 50512 KB Output is correct
8 Correct 425 ms 50036 KB Output is correct
9 Correct 486 ms 44304 KB Output is correct
10 Correct 337 ms 44112 KB Output is correct
11 Correct 244 ms 46160 KB Output is correct
12 Correct 229 ms 49216 KB Output is correct
13 Correct 281 ms 51132 KB Output is correct
14 Correct 210 ms 47400 KB Output is correct
15 Correct 32 ms 23888 KB Output is correct
16 Correct 392 ms 42448 KB Output is correct
17 Correct 248 ms 43460 KB Output is correct
18 Correct 376 ms 39900 KB Output is correct
19 Correct 398 ms 50832 KB Output is correct
20 Correct 395 ms 55584 KB Output is correct
21 Correct 311 ms 44452 KB Output is correct
22 Correct 353 ms 45136 KB Output is correct