Submission #1055284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055284		vjudge1	Pipes (CEOI15_pipes)	C++17	0 / 100	1075 ms	65536 KiB

pipes

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

const int MAXN = 1E5+16;
vector <uc> adj1[MAXN];
vector <bool> adj2[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 < adj1[u].size(); i += 2) {
        int v = frec(adj1[u][i], adj1[u][i+1], adj2[u][i>>1]);
        if (v == par) 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));
        adj2[u].push_back(f3(v));
        adj1[v].push_back(f1(u));
        adj1[v].push_back(f2(u));
        adj2[v].push_back(f3(u));
    }
    for (int u = 0; u < n; u++) {
        if (vis2[u]) continue;
        dfs(u, u);
    }
    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<unsigned char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < adj1[u].size(); i += 2) {
      |                     ~~^~~~~~~~~~~~~~~~

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