제출 #1220429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220429		LucaIlie	Pipes (CEOI15_pipes)	C++20	30 / 100	1963 ms	74148 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_LOG_N = 16;
int n;
int sef[MAX_N + 1], parent[MAX_LOG_N + 1][MAX_N + 1];
bool vis[MAX_N + 1];
vector<int> vert[MAX_N + 1];
int depth[MAX_N + 1];
int sp[MAX_N + 1];
vector<int> adj[MAX_N + 1];
vector<pair<int, int>> edges;

int findSef(int v) {
    if (sef[v] != v)
        sef[v] = findSef(sef[v]);
    return sef[v];
}

void reroot(int u, int p) {
    vis[u] = true;
    parent[0][u] = p;
    for (int l = 1; (1 << l) <= n; l++)
        parent[l][u] = parent[l - 1][parent[l - 1][u]];
    depth[u] = depth[p] + 1;
    for (int v: adj[u]) {
        if (v == p)
            continue;
        reroot(v, u);
    }
}

bool connect(int u, int v) {
    int x = findSef(u);
    int y = findSef(v);
    if (x == y)
        return true;

    // if (vert[x].size() < vert[y].size())
    //     swap(x, y);

    // reroot(v, u);

    // for (int l = 1; (1 << l) <= n; l++) {
    //     for (int v: vert[y])
    //         parent[l][v] = parent[l - 1][parent[l - 1][v]];
    // }
    // for (int a: vert[y])
    //     vert[x].push_back(a);
    // vert[y].clear();

    sef[y] = x;
    adj[u].push_back(v);
    adj[v].push_back(u);

    return false;
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) 
        swap(u, v);

    for (int l = log2(n); l >= 0; l--) {
        if (depth[v] - (1 << l) >= depth[u]) 
            v = parent[l][v];
    }

    if (u == v)
        return u;

    for (int l = log2(n); l >= 0; l--) {
        if (parent[l][u] != parent[l][v]) {
            u = parent[l][u];
            v = parent[l][v];
        }
    }

    return parent[0][u];
}

void dfs(int u, int p) {
    // printf("%d %d\n", u, p);
    for (int v: adj[u]) {
        if (v == p)
            continue;
        dfs(v, u);
        sp[u] += sp[v];
    }
    if (p != 0 && sp[u] == 0)
        cout << u << " " << p << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;

    cin >> n >> m;
    for (int v = 1; v <= n; v++)
        sef[v] = v;
    for (int e = 0; e < m; e++) {
        int u, v;

        cin >> u >> v;
        // printf("%d %d %d\n", u, v, connect(u, v));
        if (connect(u, v))
            edges.push_back({u, v});
    }

    for (int v = 1; v <= n; v++) 
        vis[v] = false;
    for (int v = 1; v <= n; v++) {
        if (vis[v])
            continue;
        reroot(v, 0);
    }

    for (auto x: edges) {
        int u = x.first, v = x.second;
        int l = lca(u, v);
        sp[u]++;
        sp[v]++;
        sp[l] -= 2;
    }

    for (int v = 1; v <= n; v++) {
        int p = parent[0][v];
        if (p == 0)
            dfs(v, 0);
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10