제출 #1336109

#제출 시각아이디문제언어결과실행 시간메모리
1336109kokokaiPastiri (COI20_pastiri)C++20
100 / 100
247 ms69728 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<pair<int,int>> adj[N];
int c[N],h[N],d[N],vis[N],has[N],vi[N];
int ord[N],pos[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(auto [v,id]: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(auto [v,id]:adj[u]){
        if(v==p) continue;
        dfs(v,u,now);
    }
}

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,i});
        adj[v].push_back({u,i});
    }
    for(int i=1;i<=k;i++) cin>>c[i];
    bfs();
    dfs(1,0,0);
    for(int i=1;i<=k;i++){
        int u=c[i];
        has[u]=1;
    }
    for(int i=1;i<=k;i++){
        ord[i]=c[i];
    }

    sort(ord+1,ord+1+k,[&](int i,int j){
        return h[i] > h[j];
    });
    for(int i=1;i<=k;i++){
        pos[ord[i]]=i;
    }
    int ans=0;
    vector<int> vec;
    vector<int> max_rem(n + 1, -1);
    int i=1;
    while(1){
        if(i>k) break;
        ans++;
        int u=ord[i];
        vi[i]=1;
        int dis=h[u]-h[wharf[u]];
        u=wharf[u];
        vec.push_back(u);
        queue<pair<int,int>> q;

        // Bắt đầu BFS nếu BFS hiện tại có bán kính phủ (dis) tốt hơn mốc lịch sử tại u
        if (dis > max_rem[u]) {
            q.push({u,0});
            max_rem[u] = dis;
        }

        while(!q.empty()){
            int curr = q.front().fi;
            int di = q.front().se;
            q.pop();

            if(has[curr]){
                vi[pos[curr]]=1;
            }
            if(di == dis) continue;

            for(auto [v,id]:adj[curr]){
                int rem = dis - (di + 1);
                // Pruning: Chỉ lan sang v và push vào queue nếu sức đi tiếp tốt hơn lịch sử
                if(rem > max_rem[v]){
                    max_rem[v] = rem;
                    q.push({v, di + 1});
                }
            }
        }
        while(vi[i]) i++;
    }
    cout<<ans<<'\n';
    for(int v:vec) cout<<v<<' ';
}

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

pastiri.cpp: In function 'int main()':
pastiri.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         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...