Submission #876865

#TimeUsernameProblemLanguageResultExecution timeMemory
876865hyakupPipes (CEOI15_pipes)C++17
0 / 100
2780 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define bug(x) cout << #x << " " << x << endl; const int maxn = 1e5 + 10; vector<int> v, pai( maxn ), tam( maxn, 1 ); vector<pair< int, int >> edge( maxn, pair< int, int>( -1, -1 ) ); int find( int a ){ if( a == pai[a] ) return a; if( edge[a] != make_pair( -1, -1 ) ) v.push_back(a); return find(pai[a]); } void join( int a, int b ){ v.clear(); int _a = find(a); int _b = find(b); if( _a == _b ){ for( int x : v ) edge[x] = make_pair( -1, -1 ); return; } if( tam[_a] < tam[_b] ) swap( _a, _b ); tam[_a] += tam[_b]; pai[_b] = _a; edge[_b] = make_pair(a, b); } int main(){ int n, m; cin >> n >> m; for( int i = 1;i <= n; i++ ) pai[i] = i; while( m-- ){ int a, b; cin >> a >> b; join( a, b ); } for( int i = 1; i <= n; i++ ){ if( edge[i] != make_pair( -1, -1 ) ) cout << edge[i].first << " " << edge[i].second << endl; } }
#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...