Submission #113024

#TimeUsernameProblemLanguageResultExecution timeMemory
113024Mahdi_JfriPipes (CEOI15_pipes)C++14
100 / 100
4335 ms16052 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 1e5 + 20; const int maxb = 20; int st[maxn] , ft[maxn] , now = -1 , par[maxn][maxb] , p[maxn] , val[maxn]; vector<int> adj[maxn]; bitset<maxn * 100> is; bool visited[maxn]; int root(int v) { return (p[v] < 0? v : p[v] = root(p[v])); } bool merge(int v , int u) { v = root(v) , u = root(u); if(v == u) return 0; if(-p[v] < -p[u]) swap(v , u); p[v] += p[u]; p[u] = v; return 1; } bool is_par(int v , int u) { return st[v] <= st[u] && st[u] <= ft[v]; } int lca(int v , int u) { for(int i = maxb - 1; i >= 0; i--) if(!is_par(par[v][i] , u)) v = par[v][i]; if(is_par(v , u)) return v; else return par[v][0]; } void dfs(int v , int p = -1) { if(p == -1) for(int i = 0; i < maxb; i++) par[v][i] = v; visited[v] = 1; st[v] = ++now; for(auto u : adj[v]) if(u != p) { par[u][0] = v; for(int i = 1; i < maxb; i++) par[u][i] = par[par[u][i - 1]][i - 1]; dfs(u , v); } ft[v] = now; } void solve(int v , int p = -1) { visited[v] = 1; for(auto u : adj[v]) if(u != p) solve(u , v) , val[v] += val[u]; if(p != -1 && !val[v]) cout << v + 1 << " " << p + 1 << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(p , -1 , sizeof p); int n , m; cin >> n >> m; for(int i = 0; i < m; i++) { int a , b; cin >> a >> b; a-- , b--; if(!merge(a , b)) is[i] = 1; else adj[a].pb(b) , adj[b].pb(a); } for(int i = 0; i < n; i++) if(!visited[i]) dfs(i); cin.seekg(0); cin >> n >> m; for(int i = 0; i < m; i++) { int a , b; cin >> a >> b; a-- , b--; if(is[i]) { int c = lca(a , b); val[a]++ , val[b]++ , val[c] -= 2; } } memset(visited , 0 , sizeof visited); for(int i = 0; i < n; i++) if(!visited[i]) solve(i); }
#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...