Submission #656042

#	Time	Username	Problem	Language	Result	Execution time	Memory
656042		mhn2	Network (BOI15_net)	C++17	100 / 100	789 ms	160724 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const int N = 5e5+5;
vector<int> adj[N], lo[N], ch[N];
vector<pii> edge;

void dfs1(int v, int p) {
    for (int u : adj[v])
        if (u != p) {
            ch[v].push_back(u);
            dfs1(u, v);
        }
}

void dfs2(int v) {
    if (ch[v].size() == 0) {
        lo[v].push_back(v);
        return;
    }

    vector<int> a, b;
    for (int u : ch[v]) {
        dfs2(u);
        if (lo[u].size() == 2) {
            a.push_back(lo[u][0]);
            a.push_back(lo[u][1]);
        }
        else
            b.push_back(lo[u][0]);
    }
    for (int x : b)
        a.push_back(x);
    
    lo[v].push_back(a[0]);
    for (int i = 1; i < a.size()-1; i += 2)
        edge.push_back({a[i], a[i+1]});
    if (!(a.size() & 1))
        lo[v].push_back(a.back());
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, r;
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (r = 1; r <= n; r++)
        if (adj[r].size() == 1)
            break;

    dfs1(r, r);
    dfs2(r);

    for (int x : lo[r])
        edge.push_back({r, x});
    
    cout << edge.size() << endl;
    for (pii x : edge)
        cout << x.F << ' ' << x.S << endl;
}

Compilation message (stderr)

net.cpp: In function 'void dfs2(int)':
net.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 1; i < a.size()-1; i += 2)
      |                     ~~^~~~~~~~~~~~

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