Submission #79572

#	Time	Username	Problem	Language	Result	Execution time	Memory
79572		Vinhspm	Network (BOI15_net)	C++14	0 / 100	15 ms	12392 KiB

net

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

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;

const int N = 5e5 + 10;
const int oo = 1e9;

int n;
int deg[N], sz[N], tmp[N];
bool visit[N];
vector<int> lef, rig, vi[N];

void dfs(int pre, int u)    {
    sz[u] = 1;
    for(int v: vi[u]) if(v != pre)
        dfs(u, v), sz[u] += sz[v];
    // :D
}

void findcen(int pre, int u, int sz1, bool spm)   {
    if(spm) visit[u] = true;
    if(!spm)    {
        for(int v: vi[u]) if(v != pre && sz[v] * 2 >= sz1)   {
            findcen(u, v, sz1, 0);
            return;
        }
    }
    visit[u] = true;
    for(int v: vi[u]) if(v != pre) findcen(u, v, sz1, 1);
}

void calc(int pos, bool spm)    {
    int cnt = 0;
    for(int i = pos; i <= n; ++i) if(visit[i] == spm && deg[i] == 1)
        tmp[++cnt] = i;
    for(int i = 1; i <= cnt - 1; i += 2) cout << tmp[i] << ' ' << tmp[i + 1] << '\n';
    if(cnt % 2 == 1) for(int i = 1; i <= n; ++i) if(visit[i] == 1 - spm && deg[i] == 1) {
        cout << i << ' ' << tmp[cnt]; exit(0);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        vi[u].pb(v); vi[v].pb(u);
        deg[u] ++; deg[v] ++;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) ans ++;
    dfs(1, 1);
    findcen(1, 1, sz[1], 0);
    cout << (ans + 1) / 2 << '\n';
    int ptr1 = 1, ptr2 = 1;
    while(visit[ptr1] || deg[ptr1] > 1) ptr1 ++;
    while(!visit[ptr2] || deg[ptr2] > 1) ptr2 ++;
    while(ptr1 <= n && ptr2 <= n)   {
        cout << ptr1 << ' ' << ptr2 << '\n';
        ptr1 ++; ptr2 ++;
        while((visit[ptr1] || deg[ptr1] != 1)) {
            ptr1 ++;
            if(ptr1 > n) break;
        }
        while((!visit[ptr2] || deg[ptr2] != 1)) {
            ptr2 ++;
            if(ptr2 > n) break;
        }
    }

    if(ptr1 <= n)   calc(ptr1, 0);
    if(ptr2 <= n) calc(ptr2, 1);
}

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