Submission #1197128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197128		HasanV11010238	Pipes (CEOI15_pipes)	C++20	100 / 100	561 ms	7084 KiB

pipes

#include <bits/stdc++.h>
#define ll long long
#define MAX 100000
#define INF 1000000000000000
#define mod 998244353
using namespace std;
ll ans[MAX + 1];
vector<vector<int>> v;
mt19937_64 rng(time(0));
int p[MAX + 1];
int find(int x){
    if (p[x] < 0) return x;
    return p[x] = find(p[x]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (a == b) return;
    if (p[a] > p[b]) swap(a, b);
    p[a] += p[b];
    p[b] = a;
}
void dfs(int x, int p){
    for (auto el : v[x]){
        if (el != p){
            dfs(el, x);
            ans[x] ^= ans[el];
        }
    }
    if (ans[x] == 0 && p != 0) cout<<x<<" "<<p<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, a, b;
    cin>>n>>m;
    for (int i = 1; i <= n; i++) p[i] = -1;
    v.assign(n + 1, vector<int>());
    for (int i = 0; i < m; i++){
        cin>>a>>b;
        int ra = find(a), rb = find(b);
        if (ra != rb){
            v[a].push_back(b);
            v[b].push_back(a);
            merge(ra, rb);
        }
        else{
            ll rn = rng();
            ans[a] ^= rn, ans[b] ^= rn;
        }
    }
    for (int i = 1; i <= n; i++) if (find(i) == i) dfs(i, 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