Submission #1220437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220437		LucaIlie	Pipes (CEOI15_pipes)	C++20	100 / 100	596 ms	9192 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_LOG_N = 16;
mt19937 rnd(1001);
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];

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

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

    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) {
    vis[u] = true;
    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;
        if (connect(u, v)) {
            int f = rnd();
            sp[u] ^= f;
            sp[v] ^= f;
        }
    }
    

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

    return 0;
}

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