Submission #1073372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073372		andrewp	Network (BOI15_net)	C++14	0 / 100	2 ms	12636 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, dst[N];
vector<int> g[N], le;
bool was[N];

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

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout.tie(nullptr); cerr.tie(nullptr);
        
    cin >> n;
    for (int i = 1; i <= n; i++) {
        dst[i] = 0;
        was[i] = false; 
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0, true);
    cout << le.size() - 1 << '\n';
    int mx = 0, node = 0; 
    for (int i = 0; i < le.size(); i++) { 
        if (mx < dst[le[i]]) {
            mx = dst[le[i]];
            node = le[i]; 
        }
    }
    int f = node;
    cout << 1 << ' ' << node << '\n';
    was[node] = true; 
    for (int i = 0; i < le.size(); i++) {   
        if (!was[le[i]]) { 
            for (int j = 1; j <= n; j++) {
                dst[j] = 0;
            }
            dfs(le[i], 0, false);  
            mx = 0, node = 0;
            for (int j = i + 1; j < le.size(); j++) {
                if (dst[le[j]] > mx && !was[le[j]]) {
                    mx = dst[le[j]];
                    node = le[j];
                }
            }
            if (node == 0) {
                node = f;
            }
            cout << le[i] << ' ' << node << '\n';
            was[node] = true;
        }
    }
    return 0;
}

Compilation message (stderr)

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

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