Submission #543432

#	Time	Username	Problem	Language	Result	Execution time	Memory
543432		Olympia	Network (BOI15_net)	C++17	100 / 100	702 ms	57628 KiB

net

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>

using namespace std;
class DisjointSetUnion {
    vector<int> parent, compSize;
    DisjointSetUnion (int n) {
        parent.resize(n), compSize.assign(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    int find_head (int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }
    void join (int x, int y) {
        x = find_head(x), y = find_head(y);
        if (x == y) {
            return;
        }
        if (compSize[x] > compSize[y]) {
            swap(x, y);
        }
        parent[x] = y;
        compSize[y] += compSize[x];
    }
};
vector<vector<int>> adj;
vector<int> nodes;
int root;
void dfs (int curNode, int prevNode) {
    if (adj[curNode].size() == 1) nodes.push_back(curNode);
    for (int i: adj[curNode]) {
        if (i != prevNode) {
            dfs (i, curNode);
        }
    }
}
int main () {
    int n;
    cin >> n;
    adj.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    for (int i = 0; i < n; i++) {
        if (adj[i].size() != 1) {
            root = i;
        }
    }
    dfs (root, root);
    cout << (nodes.size() + 1)/2 << '\n';
    for (int i = 0; i < (nodes.size() + 1)/2; i++) {
        cout << nodes[i] + 1 << " " << nodes[i + nodes.size()/2] + 1 << '\n';
    }


}

Compilation message (stderr)

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

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