Submission #731652

#TimeUsernameProblemLanguageResultExecution timeMemory
731652esomerPipes (CEOI15_pipes)C++17
90 / 100
5009 ms8436 KiB
#include<bits/stdc++.h> using namespace std; //~ #define endl "\n" typedef long long int ll; const int MOD = 1e9 + 7; const int N = 100000; int cnt = 1; pair<int, int> id[N], mn[N]; vector<int> adj[N]; int v[N]; bool vis[N]; struct DSU{ void init(int n){ for(int i = 0; i < n; i++) v[i] = -1; } int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);} bool unite(int x, int y){ x = get(x); y = get(y); if(x == y) return 0; if(v[x] > v[y]) swap(x, y); v[x] += v[y]; v[y] = x; return 1; } }; void DFS(int x){ id[x].first = cnt; cnt++; for(int node : adj[x]){ if(id[node].first > 0) continue; DFS(node); } id[x].second = cnt; cnt++; } void get_ans(int x, int p){ vis[x] = 1; for(int node : adj[x]){ if(node == p) continue; get_ans(node, x); mn[x].first = min(mn[x].first, mn[node].first); mn[x].second = max(mn[x].second, mn[node].second); if(!(mn[node].first < id[node].first || mn[node].second > id[node].second)){ cout << node + 1 << " " << x + 1 << endl; } } } void solve(){ int n, m; cin >> n >> m; DSU UF; UF.init(n); vector<int> done; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; if(UF.unite(v, u)) {adj[u].push_back(v); adj[v].push_back(u); done.push_back(i);} } for(int i = 0; i < n; i++) id[i] = {0, 0}; for(int i = 0; i < n; i++){ if(id[i].first == 0){ DFS(i); } } rewind(stdin); cin >> n >> m; for(int i = 0; i < n; i++) mn[i] = {id[i].first, id[i].second}; int ind = 0; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; if(ind < (int)done.size() && done[ind] == i){ ind++; continue; } mn[u].first = min(mn[u].first, id[v].first); mn[u].second = max(mn[u].second, id[v].second); mn[v].first = min(mn[v].first, id[u].first); mn[v].second = max(mn[v].second, id[u].second); } for(int i = 0; i < n; i++) vis[i] = 0; for(int i = 0; i < n; i++){ if(!vis[i]){ get_ans(i, -1); } } } signed main(){ //~ ios_base::sync_with_stdio(0); //~ cin.tie(0); //~ int tt; cin >> tt; int tt = 1; for(int t = 1; t <= tt; t++){ solve(); } }
#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...