Submission #40617

#	Time	Username	Problem	Language	Result	Execution time	Memory
40617		Hassoony	Network (BOI15_net)	C++14	100 / 100	1034 ms	175436 KiB

net

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll inf=(1ll<<60);
const ll mod=1e9+7;
const int MX=6e5+9;
int n,subtree[MX],par[MX],leaf[MX],ans;
vector<int>v[MX],v1[MX];
void dfs_size(int x,int p){
    subtree[x]=leaf[x];
    par[x]=p;
    for(auto pp:v[x]){
        if(pp==p)continue;
        dfs_size(pp,x);
        subtree[x]+=subtree[pp];
    }
}
int centroid(int x){
    dfs_size(x,-1);
    int S=subtree[x],idx=1;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int nxt=q.front();q.pop();
        int s=subtree[x]-subtree[nxt];
        for(auto pp:v[nxt]){
            if(pp==par[nxt])continue;
            s=max(s,subtree[pp]);
            q.push(pp);
        }
        if(S>s){
            S=s;
            idx=nxt;
        }
    }
    return idx;
}
int x,y,cen=1,timer;
void dfs(int x,int p){
    if(leaf[x]){
        v1[timer].push_back(x);
        return;
    }
    for(auto pp:v[x]){
        if(pp==p)continue;
        dfs(pp,x);
        if(x==cen)timer++;
    }
}
int leaves;
int cel(int x,int y){
    if(x%y==0)return x/y;
    return x/y+1;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(v[i].size()==1){
            leaf[i]=1;
            leaves++;
        }
    }
    int idx=1;
    for(int i=1;i<=n;i++)if(!leaf[i])idx=i;
    ans=cel(leaves,2);
    cen=centroid(idx);
    dfs(cen,-1);
    priority_queue<pair<int,int> >pq;
    for(int i=0;i<timer;i++){
        pq.push({v1[i].size(),i});
    }
    printf("%d\n",ans);
    while(pq.size()>1){
        int com1=pq.top().second,sz1=pq.top().first;pq.pop();
        int com2=pq.top().second,sz2=pq.top().first;pq.pop();
        if(sz1<=0||sz2<=0)continue;
        printf("%d %d\n",v1[com1].back(),v1[com2].back());
        v1[com1].pop_back();sz1--;
        v1[com2].pop_back();sz2--;
        if(sz1>0)pq.push({sz1,com1});
        if(sz2>0)pq.push({sz2,com2});
    }
    if(pq.size()==1){
        printf("%d %d",v1[pq.top().second][0],cen);
    }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:57:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
net.cpp:59:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37