Submission #79556

#	Time	Username	Problem	Language	Result	Execution time	Memory
79556		Vinhspm	Network (BOI15_net)	C++14	0 / 100	26 ms	24056 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];
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);
}

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);
    for(int i = 1; i <= n; ++i) if(deg[i] ==1) {
        if(!visit[i]) lef.pb(i);
        else rig.pb(i);
    }
    cout << (ans + 1) / 2 << '\n';
    int ptr1 = 0, ptr2 = 0;
    while(ptr1 < lef.size() && ptr2 < rig.size()) {
        cout << lef[ptr1] << ' ' << rig[ptr2] << '\n';
        ptr1 ++; ptr2 ++;
    }
    while(ptr1 < lef.size() - 1) cout << lef[ptr1] << ' ' << lef[ptr1 + 1] << '\n' , ptr1 += 2;
    if(ptr1 < lef.size()) cout << lef[ptr1] << ' ' << rig[0] << '\n';
    while(ptr2 < rig.size() - 1) cout << rig[ptr2] << ' ' << rig[ptr2 + 1] << '\n' , ptr2 += 2;
    if(ptr2 < rig.size()) cout << rig[ptr2] << ' ' << lef[0] << '\n';

    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr1 < lef.size() && ptr2 < rig.size()) {
           ~~~~~^~~~~~~~~~~~
net.cpp:57:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr1 < lef.size() && ptr2 < rig.size()) {
                                ~~~~~^~~~~~~~~~~~
net.cpp:61:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr1 < lef.size() - 1) cout << lef[ptr1] << ' ' << lef[ptr1 + 1] << '\n' , ptr1 += 2;
           ~~~~~^~~~~~~~~~~~~~~~
net.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr1 < lef.size()) cout << lef[ptr1] << ' ' << rig[0] << '\n';
        ~~~~~^~~~~~~~~~~~
net.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr2 < rig.size() - 1) cout << rig[ptr2] << ' ' << rig[ptr2 + 1] << '\n' , ptr2 += 2;
           ~~~~~^~~~~~~~~~~~~~~~
net.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr2 < rig.size()) cout << rig[ptr2] << ' ' << lef[0] << '\n';
        ~~~~~^~~~~~~~~~~~

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