Submission #232114

#	Time	Username	Problem	Language	Result	Execution time	Memory
232114		DodgeBallMan	Pipes (CEOI15_pipes)	C++14	60 / 100	1508 ms	25976 KiB

pipes

#include <bits/stdc++.h>
 
using namespace std;
#define adj(v, p) (v^E[p][0]^E[p][1])
const int N = 1e5 + 2;
int h[N], par[N], _par[N], E[2*N][2], id = 0;
bool mark[N];
vector <int> g[N];
 
 
void add(int u, int v) {
    E[++id][0] = u, E[id][1] = v;
    g[u].push_back(id), g[v].push_back(id);
    return ;
}
int getpar(int u) {return par[u] = (par[u] == u ? u : getpar(par[u]));}
int get_par(int u) {return _par[u] = (_par[u] == u ? u : get_par(_par[u]));}
void Union(int u, int v) {
    int ru = getpar(u), rv = getpar(v);
    if (ru == rv) {
        ru = get_par(u), rv = get_par(v);
        if (ru == rv) return ;
        _par[ru] = rv, add(u, v);
        return ;
    }
    par[ru] = rv, add(u, v);
    return ;
}
int dfs(int v, int p = 0) {
    mark[v] = 1;
    int mx = h[v];
    for (int i : g[v]) {
        if (!mark[adj(v, i)]) h[adj(v, i)] = h[v] + 1, mx = min(mx, dfs(adj(v, i), i));
        else if (i != p) mx = min(mx, h[adj(v, i)]);
    }
    if (p && mx == h[v]) cout << v << " " << adj(v, p) << "\n";
    return mx;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) par[i] = _par[i] = i;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        Union(u, v);
    }
    for (int i = 1; i <= n; i++) if (!mark[i]) dfs(i);
}

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