Submission #527508

#	Time	Username	Problem	Language	Result	Execution time	Memory
527508		jalsol	Network (BOI15_net)	C++11	0 / 100	8 ms	12076 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 5e5 + 5;

int n;
vector<int> g[maxN];

vector<pair<int, int>> ans;
int d[maxN];
int trace[maxN];
queue<int> q;

vector<int> child;

void Bfs(int s) {
    For (i, 1, n) {
        d[i] = -1;
        trace[i] = 0;
    }
    d[s] = 0;
    trace[s] = -1;
    q.push(s);

    while (isz(q)) {
        int u = q.front(); q.pop();

        for (int v : g[u]) {
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                trace[v] = u;
                q.push(v);
            }
        }
    }
}

void Dfs(int u, int p) {
    bool hasChild = false;

    for (int v : g[u]) {
        if (v != p) {
            hasChild = true;
            Dfs(v, u);
        }
    }

    if (!hasChild) {
        child.push_back(u);
    }
}

signed main() {
    cin >> n;

    For (i, 1, n - 1) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ans.reserve(n);
    Bfs(1);
    int s = max_element(d + 1, d + n + 1) - d;
    Bfs(s);
    int t = max_element(d + 1, d + n + 1) - d;
    ans.emplace_back(s, t);

    child.reserve(n);
    int pre = -1;

    for (int u = t; u != -1; u = trace[u]) {
        for (int v : g[u]) {
            if (v == pre || v == trace[u]) {
                continue;
            }

            Dfs(v, u);
        }

        pre = u;
    }

    Rep (i, isz(child) - 1) {
        ans.emplace_back(child[i], child[i + 1]);
    }

    cout << isz(ans) << '\n';
    for (const auto& p : ans) {
        cout << p.fi << ' ' << p.se << '\n';
    }
}

/*

*/

Compilation message (stderr)

net.cpp: In constructor '__Init__::__Init__()':
net.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
net.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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