Submission #394612

#	Time	Username	Problem	Language	Result	Execution time	Memory
394612		fammo	Network (BOI15_net)	C++11	100 / 100	938 ms	85704 KiB

net

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define endl '\n'
//#define int ll
const int  N = 500 * 1000 + 20, MOD = 1e9+7,  base =727;
int n, st[N], low[N], tim;
vector<int>adj[N], leaf;
vector<pii>g[N];
bool mark[N];
void dfs(int v, int p){
    if(int(adj[v].size()) == 1)leaf.pb(v);
    for(int u : adj[v])if(u!=p)dfs(u,v);
    return;
}void check(int v, int e){
    st[v] = low[v] = ++tim;
    mark[v] = 1;
    for(auto p : g[v]){
        int u = p.first, i = p.second;
        if(!mark[u]){
            check(u, i);
            low[v] = min(low[u], low[v]);
            if(low[u] > st[v])
                while(1)tim++;
        }
        else if(i != e)
            low[v] = min(low[v], st[u]);
    }
    return;
}
int32_t main(){
    fastio;
    ///auto t = clock();
    cin >> n;
    for(int i = 0; i < n - 1; i ++){
        int u, v;
        cin >> u >> v;
        u --; v --;
        adj[u].pb(v); adj[v].pb(u);
        g[v].pb({u,i}); g[u].pb({v,i});
    }int root = 0;
    for(int i = 0; i < n; i ++){if(int(adj[i].size()) >2){root = i;}}
    if(int(adj[root].size()<=2)){
        cout << 1 << endl;
        for(int i =0 ; i < n; i ++)if((int)adj[i].size() == 1)cout << i +1 << ' ';
        cout << endl;
        return 0;
    }
    dfs(root,-1);
    int k = (int(leaf.size()))/2;
    int ans  = (int(leaf.size()) + 1)/2;
    for(int i = 0; i < ans; i ++){
        int u = leaf[i], v = leaf[i+k];
        g[v].pb({u,i+n-1}); g[u].pb({v,i+n-1});
    }
    check(root,-1);
    cout << ans << endl;
    for(int i = 0; i < ans; i ++){
        cout << leaf[i] + 1 << ' ' << leaf[i+k] + 1 << endl;
    }
    ///cout << clock() - t << "ms" << endl;
    return 0;

}

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