Submission #1213439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213439		minhpk	Network (BOI15_net)	C++20	100 / 100	261 ms	96388 KiB

net

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
vector <int> z[1000005];
int root;
int par[1000005];
vector <int> sz[1000005];
int k;
int find(int u){
    if (par[u]==u){
        return u;
    }
    return par[u]=find(par[u]);
}
void join(int x,int y){
    x=find(x);
    y=find(y);

    if (x==y){
        return;
    }
    while ( (sz[x].size()>1 || sz[y].size()>1) && sz[x].size() && sz[y].size()){
          cout << sz[x].back() << " " << sz[y].back() << "\n";
          sz[x].pop_back();
          sz[y].pop_back();
    }
    par[y]=x;
    while (sz[y].size()){
         int p=sz[y].back();
         sz[x].push_back(p);
         sz[y].pop_back();
    }
}
void dfs(int i,int parent){

    for (auto p:z[i]){
         if (p==parent){
            continue;
         }
         dfs(p,i);
         join(i,p);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    for (int i=1;i<=a;i++){
         if (z[i].size()!=1){
             root=i;
         }
    }
    for (int i=1;i<=a;i++){
         par[i]=i;
    }
    for (int i=1;i<=a;i++){
         if (z[i].size()==1){
             sz[i].push_back(i);
             k++;
         }
    }
    cout << (k+1)/2 << "\n";
    dfs(root,0);
    int x=find(root);
    if (sz[x].size()%2==0){
        for (int i=0;i<sz[x].size();i+=2){
             cout << sz[x][i] << " " << sz[x][i+1] << "\n";
        }
    }else{
        sz[x].push_back(root);
        for (int i=0;i<sz[x].size();i+=2){
             cout << sz[x][i] << " " << sz[x][i+1] << "\n";
        }
    }

    return 0;
}

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