Submission #1163782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163782		AlgorithmWarrior	Network (BOI15_net)	C++20	100 / 100	394 ms	105628 KiB

net

#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int const MAX=5e5+5;
int n;
vector<int>tree[MAX];
vector<pii>rasp;
int root;

void read(){
    cin>>n;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}

pii dfs(int nod,int tata){
    if(tree[nod].size()==1)
        return {nod,0};
    vector<int>solo;
    vector<pii>duo;
    for(auto fiu : tree[nod])
        if(fiu!=tata){
            auto per=dfs(fiu,nod);
            if(per.second==0)
                solo.push_back(per.first);
            else
                duo.push_back(per);
        }
    int i;
    if(duo.size()>1){
        for(i=0;i<(int)duo.size()-1;++i)
            rasp.push_back({duo[i].second,duo[i+1].first});
        rasp.push_back({duo[0].first,duo.back().second});
        duo.clear();
    }
    if(duo.size()==1){
        if(solo.size()==1){
            swap(solo[0],duo[0].first);
            rasp.push_back(duo[0]);
            duo.clear();
        }
        else
        if(solo.size()>1){
            rasp.push_back({duo[0].second,solo.back()});
            solo.pop_back();
            rasp.push_back({duo[0].first,solo.back()});
            solo.pop_back();
            duo.clear();
        }
    }
    while(solo.size()>=2){
        int nod1=solo.back();
        solo.pop_back();
        int nod2=solo.back();
        solo.pop_back();
        rasp.push_back({nod1,nod2});
    }
    if(nod==root){
        if(solo.size()==1){
            rasp.push_back({solo[0],root});
            solo.clear();
        }
        return {0,0};
    }
    else{
        if(solo.size()==1)
            return {solo[0],0};
        if(duo.size()==1)
            return duo[0];
        auto per=rasp.back();
        rasp.pop_back();
        return per;
    }
}

void write(){
    cout<<rasp.size()<<'\n';
    for(auto [u,v] : rasp)
        cout<<u<<' '<<v<<'\n';
}

void find_root(){
    int i;
    for(i=1;i<=n;++i)
        if(tree[i].size()>1)
            root=i;
}

int main()
{
    read();
    find_root();
    dfs(root,0);
    write();
    return 0;
}

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