제출 #1081692

#제출 시각아이디문제언어결과실행 시간메모리
1081692TB_Pipes (CEOI15_pipes)C++17
100 / 100
721 ms5340 KiB
#include <bits/stdc++.h> using namespace std; #define ll int #define fo(i, n) for(ll i = 0; i<(n); i++) #define F first #define S second #define pb push_back #define deb(x) cout << #x << " = " << (x) << endl #define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl typedef vector<int> vl; typedef vector<vl> vvl; struct UnionFind{ int n; vl p; UnionFind(int n){ p.resize(n); fo(i, n) p[i] = i; } int find(int x){ if(p[x] == x) return x; return p[x] = find(p[x]); } bool same(int a, int b){ return find(a) == find(b); } void unite(int a, int b){ a = find(a); b = find(b); if(rand()%2) swap(a, b); p[b] = a; } }; int main(){ cin.tie(0)->sync_with_stdio(0); int n, m, from, to; cin >> n >> m; vl xorv(n, 0), amount(n, 0), hash(n, 0); UnionFind uf(n); mt19937 rng(42); fo(i, m){ cin >> from >> to; from--; to--; if(uf.same(from, to)){ ll val = rng(); hash[from]^=val; hash[to]^=val; }else{ amount[from]++; amount[to]++; xorv[from]^=to; xorv[to]^=from; uf.unite(from, to); } } ll pos; fo(i, n){ pos=i; while(1){ if(amount[pos] != 1) break; ll edge = xorv[pos]; if(!hash[pos]) cout << pos+1 << " " << edge+1 << endl; amount[pos]--; amount[edge]--; xorv[pos]^=edge; xorv[edge]^=pos; hash[edge]^=hash[pos]; pos = edge; if(amount[edge] != 1) break; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...