Submission #211758

#	Time	Username	Problem	Language	Result	Execution time	Memory
211758		mayhoubsaleh	Network (BOI15_net)	C++14	0 / 100	13 ms	12160 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;
const ll inf=1e9+10;
const ll maxn=5e5+100;
int n;
vector<int>v[maxn],leaf;
int x[maxn],y[maxn];
vector<pair<int,int>>ans;
void dfs(int nod,int par){
    if(v[nod].size()==1)leaf.pb(nod);
    for(auto ch:v[nod]){
        if(ch==par)continue;
        dfs(ch,nod);
    }
}
int d[2],dist[maxn][2];
pair<int,int>getfar(int nod,int par,int dep){
    pair<int,int>ret={dep,nod};
    for(auto ch:v[nod]){
        if(ch==par)continue;
        ret=max(ret,getfar(ch,nod,dep+1));
    }
    return ret;
}

inline void diam(){
    auto el=getfar(1,0,0);
    d[0]=el.second;
    el=getfar(d[0],0,0);
    d[1]=el.second;
}

void dfs(int nod,int par,int dep,bool k){
    dist[nod][k]=dep;
    for(auto x:v[nod]){
        if(x==par)continue;
        dfs(x,nod,dep+1,k);
    }
}

bool com0(int x,int y){
    return dist[x][0]>dist[y][0];
}

bool com1(int x,int y){
    return dist[x][1]>dist[y][1];
}

bool vis[maxn];
int main()
{
    IOS
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }

    diam();
    //cout<<d[0]<<' '<<d[1]<<endl;
    dfs(d[0],0,0,0);
    dfs(d[1],0,0,1);

    for(int i=0;i<n;i++){
        x[i]=i+1;
        y[i]=i+1;
    }
    sort(x,x+n,com0);
    sort(y,y+n,com1);
    //for(int i=0;i<n;i++)cout<<x[i]<<' ';cout<<endl;
    //for(int i=0;i<n;i++)cout<<y[i]<<' ';cout<<endl;

    int cur0=0,cur1=0;
    while(cur0<n&&cur1<n){
        if(vis[x[cur0]]||v[x[cur0]].size()>1){cur0++;continue;}
        if(vis[y[cur1]]||v[y[cur1]].size()>1){cur1++;continue;}
        if(x[cur0]==y[cur1]){cur0++;continue;}
        ans.pb({x[cur0],y[cur1]});
        vis[x[cur0]]=1;
        vis[y[cur1]]=1;
        cur0++;
        cur1++;
    }
    //cout<<cur0<<' '<<cur1<<endl;
    int l0=cur0,r0=n-1;
    while(l0<r0){
        if(v[x[l0]].size()>1||vis[x[l0]]){l0++;continue;}
        if(v[x[r0]].size()>1||vis[x[r0]]){r0--;continue;}
        ans.pb({x[l0],x[r0]});
        vis[x[l0]]=1;
        vis[x[r0]]=1;
        l0++;
        r0--;
    }
    if(l0==r0&&v[x[r0]].size()==1&&!vis[x[r0]]){
        if(x[r0]==d[0])ans.pb({x[r0],d[1]});
        else ans.pb({x[r0],d[0]});
    }

    int l1=cur1,r1=n-1;
    while(l1<r1){
        if(v[y[l1]].size()>1||vis[y[l1]]){l1++;continue;}
        if(v[y[r1]].size()>1||vis[y[r1]]){r1--;continue;}
        ans.pb({y[l1],y[r1]});
        vis[y[l1]]=1;
        vis[y[r1]]=1;
        l1++;
        r1--;
    }
    if(l1==r1&&v[y[r1]].size()==1&&!vis[y[r1]]){
        if(y[r1]==d[0])ans.pb({y[r1],d[1]});
        else ans.pb({y[r1],d[0]});
    }

    cout<<ans.size()<<endl;
    for(auto it:ans){
        cout<<it.first<<' '<<it.second<<endl;
    }
    return 0;
}

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