Submission #401861

#	Time	Username	Problem	Language	Result	Execution time	Memory
401861		gevacrt	Network (BOI15_net)	C++17	100 / 100	768 ms	173008 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()

namespace CHECK_GRAPH {
    vi tin, low, vis; int timer = 0; 

    bool pos = true;
    int dfs(int u, int p, vvi &adj){
        vis[u] = 1; tin[u] = low[u] = timer++;
        
        bool so = false;
        for(auto v : adj[u]){
            if(v == p and !so) {so = true; continue;}
            if(vis[v]) low[u] = min(low[u], tin[v]);
            else low[u] = min(low[u], dfs(v, u, adj));
        }

        if(tin[u] == low[u] and u != p) pos = false;
        return low[u];
    }

    void init(vvi &adj, int ROOT){
        int N = adj.size();
        tin.resize(N), low.resize(N);
        vis.resize(N); dfs(ROOT, ROOT, adj);
    }
};


vvi adj; vii bb;

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

    vvi vec1, vec2;
    for(auto v : adj[u]){
        if(v == p) continue;
        if(auto vec = solve(v, u); vec.size() == 1)
            vec1.push_back(vec);
        else vec2.push_back(vec);
    }

    vi vec;
    auto ss = [&](vi nvec){
        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));
    };

    for(auto vv : vec2) ss(vv);
    for(auto vv : vec1) ss(vv);


    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";
        adj[u].push_back(v); adj[v].push_back(u);
    }

    CHECK_GRAPH::init(adj, ROOT);
    assert(CHECK_GRAPH::pos);

    return 0;
}

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