Submission #1073376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073376		andrewp	Network (BOI15_net)	C++14	0 / 100	3 ms	12124 KiB

net

//Dedicated to my love, ivaziva 
#include <bits/stdc++.h>
using namespace std; 

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';  

constexpr int N = 5e5 + 20;
int n;
vector<int> g[N], le; 

void dfs(int x, int p) {
    if (g[x].size() == 1 && g[x][0] == p) {
        le.push_back(x); 
    }
    for (int u: g[x]) {
        if (u != p) { 
            dfs(u, x);  
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout.tie(nullptr); cerr.tie(nullptr);
        
    cin >> n; 
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() > 1) {
            root = i;
        }
    }
    dfs(root, 0);
    vector<pii> ans; 
    for (int x: le) {
        cout << x << ' ';
    }
    cout << '\n';
    for (int i = 0; i < le.size() / 2; i++) {
        ans.push_back({le[i], le[le.size() / 2 + i]});
    }
    if (le.size() & 1) {
        ans.push_back({le[0], le.back()});  
    }
    cout << ans.size() << '\n';
    for (auto ptr: ans) {
        cout << ptr.first << ' ' << ptr.second << '\n';
    }
    return 0;
}

Compilation message (stderr)

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

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