제출 #1336083

#제출 시각아이디문제언어결과실행 시간메모리
1336083kokokaiPastiri (COI20_pastiri)C++20
8 / 100
1101 ms110228 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define task "text"
#define fi first
#define se second
const int N = 5e5+5;
vector<int> adj[N];
int c[N],h[N],d[N],vis[N],has[N];
int wharf[N];
int n,k;
void bfs(){
    queue<int> q;
    for(int i=1;i<=n;i++) d[i]=1e9;
    for(int i=1;i<=k;i++){
        d[c[i]]=0;
        q.push(c[i]);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:adj[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}
void dfs(int u,int p,int now){
    h[u]=h[p]+1;
    if(h[u]+d[u] > h[now]+d[now]){
        now=u;
    }
    wharf[u]=now;
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u,now);
    }
}
map<pair<int,int>,int> mp;
int findid(int u,int v){
    if(u>v) swap(u,v);
    return mp[{u,v}];
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if(u>v) swap(u,v);
        mp[{u,v}]=i;
    }
    for(int i=1;i<=k;i++) cin>>c[i];
    bfs();
    dfs(1,0,0);
    set<pair<int,int>> s;
    for(int i=1;i<=k;i++){
        int u=c[i];
        has[u]=1;
        s.insert({h[u],u});
    }
    int ans=0;
    vector<int> vec;
    //cerr<<wharf[1]<<' '<<wharf[4]<<'\n';
    for(int i=1;i<=k;i++){
        //cerr<<c[i]<<' '<<wharf[c[i]]<<'\n';
    }
    while(!s.empty()){
        ans++;
        int u=s.rbegin()->se;
        //cerr<<u<<'\n';
        queue<pair<int,int>> q;
        int dis=h[u]-h[wharf[u]];
        u=wharf[u];
        vec.push_back(u);
        q.push({u,0});
        while(!q.empty()){
            int u=q.front().fi;
            int di=q.front().se;
            q.pop();
            if(has[u]){
                if(s.find({h[u],u}) != s.end()) s.erase(s.find({h[u],u}));
            }
            if(di == dis) continue;
            for(int v:adj[u]){
                int id=findid(u,v);
                if(!vis[id]){
                    vis[id]=1;
                    q.push({v,di+1});
                }
            }

        }

    }
    cout<<ans<<'\n';
    for(int v:vec) cout<<v<<' ';
}

컴파일 시 표준 에러 (stderr) 메시지

pastiri.cpp: In function 'int main()':
pastiri.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...