Submission #1215228

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

net

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

void tarjan(int u, int p, vector<vector<int>> &adj, vector<int> &tin, vector<int> &low, vector<bool> &vis, int &timer, bool &is_bridge) {
    vis[u] = true;
    tin[u] = low[u] = timer++;

    for (auto &v : adj[u]) {
        if (v == p) continue;
        if (vis[v]) {
            low[u] = min(low[u], tin[v]);
            continue;
        }
        tarjan(v, u, adj, tin, low, vis, timer, is_bridge);
        low[u] = min(low[u], low[v]);
        is_bridge = is_bridge || (low[v] > tin[u]);
    }
}

bool has_bridge(vector<vector<bool>> &adjmat) {
    int n = adjmat.size();
    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (adjmat[i][j] != 1) continue;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }

    vector<int> tin(n, -1); vector<int> low(n, -1); vector<bool> vis(n, false); int timer = 0; bool is_bridge = false;
    tarjan(0, 0, adj, tin, low, vis, timer, is_bridge);
    return is_bridge;
}

const int MAXLOG = 18;
int n, timer = 0;
vector<vector<int>> adj, up; vector<pair<int, int>> edges;
vector<int> sz, leaves, tin, tout, depth;

void get_subtree_size(int u, int p) {
    sz[u] = 1;
    for (auto &v : adj[u]) {
        if (v == p) continue;
        get_subtree_size(v, u);
        sz[u] += sz[v];
    }

    if (sz[u] == 1 && p != -1) leaves.push_back(u);
}

int find_centroid(int u, int p) {
    for (auto &v : adj[u]) {
        if (v == p) continue;
        if (sz[v] * 2 > n) return find_centroid(v, u);
    }

    return u;
}

void dfs(int u, int p) {
    tin[u] = timer++;

    if (u == 0) depth[u] = 0;
    else depth[u] = depth[p] + 1;

    up[u][0] = p;
    for (int i = 1; i < MAXLOG; i++) {
        up[u][i] = up[up[u][i - 1]][i-1];
    }

    for (auto &v : adj[u]) {
        if (v == p) continue;

        dfs(v, u);
    }

    tout[u] = timer;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int find_lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) {
            u = up[u][i];
        }
    }

    return up[u][0];
}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[find_lca(u, v)];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    adj.assign(n, vector<int>()); sz.assign(n, -1);
    tin.assign(n, 0); tout.assign(n, 0); depth.assign(n, 0);
    up.assign(n, vector<int>(MAXLOG, 0));
    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);
        edges.push_back({u, v});
    }
    
    get_subtree_size(0, -1);
    int centre = find_centroid(0, -1);
    leaves.clear(); get_subtree_size(centre, -1);
    dfs(centre, centre);

    vector<pair<int, int>> new_edges;

    set<int> lset(leaves.begin(), leaves.end());
    while (!lset.empty()) {
        int curnode = *lset.begin();
        lset.erase(curnode);
        int endnode = -1, end_dist = -1;

        for (auto &v : lset) {
            int vd = dist(curnode, v);
            if (vd > end_dist) endnode = v, end_dist = vd;
        }

        lset.erase(endnode);
        new_edges.push_back({curnode+1, endnode+1});
        if (lset.size() == 1) {
            int nnc = *lset.begin();
            lset.erase(nnc);
            new_edges.push_back({nnc+1, endnode+1});
        }
    }

    cout << new_edges.size() << "\n";
    for (auto &el : new_edges) {
        cout << el.first << " " << el.second << "\n";
    }
    return 0;
}

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