Submission #401841

#	Time	Username	Problem	Language	Result	Execution time	Memory
401841		gevacrt	Network (BOI15_net)	C++17	0 / 100	1 ms	204 KiB

net

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

vvi adj; vii bb;

vi solve(int u, int p){
    if(adj[u].size() == 1) return {u};

    vi vec;
    for(auto v : adj[u]){
        if(v == p) continue;

        vi nvec = solve(v, u);
        while(vec.size() and nvec.size() and vec.size()+nvec.size() > 2-(u==p)){
            bb.push_back({vec.back(), nvec.back()});
            vec.pop_back(); nvec.pop_back();
        }
        vec.insert(vec.end(), all(nvec));
    }

    if(u == p and vec.size()){
        bb.push_back({vec.back(), u});
    }

    return vec;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N; cin >> N;
    adj.resize(N);

    for(int x = 0; x < N-1; x++){
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ROOT = 0;
    for(int x = 0; x < N; x++)
        if(adj[x].size() > 1) ROOT = x; 

    solve(ROOT, ROOT);

    cout << bb.size() << endl;
    for(auto [u, v] : bb)
        cout << u+1 << " " << v+1 << "\n";

    return 0;
}

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