Submission #1055304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055304		vjudge1	Pipes (CEOI15_pipes)	C++17	40 / 100	499 ms	41552 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
using vi = vector <int>;
using uc = unsigned char;

const int MAXN = 8E4;
vector <uc> adj1[MAXN];
vector <uc> adj2[MAXN];
int deg[MAXN];
bitset <MAXN> vis1, vis2;
int tin[MAXN], fup[MAXN], timer = 0;

uc f1 (int x) { return x&0xff; }
uc f2 (int x) { return x>>8&0xff; }
bool f3 (int x) { return x>>16&1; }
int frec (uc v1, uc v2, bool v3) { return int(v1)|int(v2)<<8|int(v3)<<16; }

void dfs (int u, int par) {
    vis1[u] = true;
    fup[u] = tin[u] = timer++;
    for (int i = 0; i < deg[u]; i++) {
        int v = frec(adj1[u][i<<1], adj1[u][i<<1|1], bool(adj2[u][i>>3]>>(i&7)&1));
        if (v == par) { par = u; continue; }
        if (vis2[v]) continue;
        if (vis1[v]) {
            fup[u] = min(fup[u], tin[v]);
        } else {
            dfs(v, u);
            fup[u] = min(fup[u], fup[v]);
            if (fup[v] == tin[v]) { // bridge (u, v)
                cout << u+1 << ' ' << v+1 << '\n';
            }
        }
    }
    vis2[u] = true;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adj1[u].push_back(f1(v));
        adj1[u].push_back(f2(v));
        if ((deg[u]&7) == 0) adj2[u].push_back(0);
        adj2[u].back() |= f3(v)<<(deg[u]&7);
        adj1[v].push_back(f1(u));
        adj1[v].push_back(f2(u));
        if ((deg[v]&7) == 0) adj2[v].push_back(0);
        adj2[v].back() |= f3(u)<<(deg[v]&7);
        deg[u]++; deg[v]++;
    }
    for (int u = 0; u < n; u++) {
        if (vis2[u]) continue;
        dfs(u, u);
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 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