Submission #1189430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189430		hehe	Network (BOI15_net)	C++20	0 / 100	0 ms	328 KiB

net

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> depth, low;
set<int> final;
vector<bool> visited;
int distanta = 0;

void dfs(int u, int parent) {
    visited[u] = true;
    depth[u] = low[u] = distanta++;
    int children = 0;

    for (int v : adj[u]) {
        if (v == parent) continue;

        if (!visited[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if ((parent == -1 && ++children > 1) || (parent != -1 && low[v] >= depth[u]))
                final.insert(u);
        } else {
            low[u] = min(low[u], depth[v]);
        }
    }
}

int main() {
    int n, a, b;
    cin >> n;
    adj.resize(n + 1);
    depth.resize(n + 1);
    low.resize(n + 1);
    visited.assign(n + 1, false);

    for (int i = 0; i < n - 1; ++i) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(1, -1);

    vector<int> deg(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (final.count(i)) {
            for (int v : adj[i])
                if (!final.count(v))
                    deg[v]++;
        }
    }

    vector<int> leaves;
    for (int i = 1; i <= n; ++i)
        if (!final.count(i) && deg[i] == 1)
            leaves.push_back(i);

    cout << (leaves.size() + 1) / 2 << "\n";
    for (int i = 0; i + 1 < leaves.size(); i += 2)
        cout << leaves[i] << " " << leaves[i + 1] << "\n";
        
        
    if (leaves.size() % 2 == 1) {
    int leaf = leaves.back();
    int fallback = *final.begin(); 
    cout << leaf << " " << fallback << "\n";
    }

}

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