Submission #877193

#	Time	Username	Problem	Language	Result	Execution time	Memory
877193		khueprovip	Pastiri (COI20_pastiri)	C++17	100 / 100	486 ms	88344 KiB

pastiri

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

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