Submission #79553

#	Time	Username	Problem	Language	Result	Execution time	Memory
79553		Vinhspm	Network (BOI15_net)	C++14	0 / 100	30 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] ++;
    }
    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);
    }
    vector<ii> ans;
    int ptr1 = 0, ptr2 = 0;
    while(ptr1 < lef.size() && ptr2 < rig.size()) {
        ans.pb(ii(lef[ptr1], rig[ptr2]));
        ptr1 ++; ptr2 ++;
    }
    while(ptr1 < lef.size() - 1) ans.pb(ii(lef[ptr1], lef[ptr1 + 1])), ptr1 += 2;
    if(ptr1 < lef.size()) ans.pb(ii(lef[ptr1], rig[0]));
    while(ptr2 < rig.size() - 1) ans.pb(ii(rig[ptr2], rig[ptr2 + 1])), ptr2 += 2;
    if(ptr2 < rig.size()) ans.pb(ii(rig[ptr2], lef[0]));
    cout << ans.size() << '\n';
    for(ii v: ans) cout << v.fi << ' ' << v.se << '\n';
}

Compilation message (stderr)

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

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