Submission #1021665

#TimeUsernameProblemLanguageResultExecution timeMemory
1021665idiotcomputerPipes (CEOI15_pipes)C++11
0 / 100
709 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz size const int mxN = 1e5; vector<int> adj[mxN]; int d[mxN]; int low[mxN]; void dfs(int c, int depth, int p){ d[c] = depth; low[c] = d[c]; int op = p; for (int i : adj[c]){ if (i == p){p = -1; continue;} if (d[i] != -1){ low[c] = min(low[c],d[i]); continue;} dfs(i,depth+1,c); low[c] = min(low[c], low[i]); } if (low[c] >= depth && op != -1) cout << c+1 << " " << op+1 << '\n'; } int p[mxN][2]; int ssize[mxN][2]; int gpar(int c, int w){ if (p[c][w] == c) return c; p[c][w] = gpar(p[c][w],w); return p[c][w]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) {p[i][j] = i; ssize[i][j] = 1;} int a,b; int x,y; int cnt = 0; for (int i = 0; i < m; i++){ cin >> a >> b; a -= 1; b -= 1; x = gpar(a,0); y = gpar(b,0); if (x != y){ //adj[a].pb(b); // adj[b].pb(a); cnt++; if (ssize[x][0] < ssize[y][0]) swap(x,y); ssize[x][0] += ssize[y][0]; p[y][0] = x; continue; } x = gpar(a,1); y = gpar(b,1); if (x == y) continue; if (ssize[x][1] < ssize[y][1]) swap(x,y); ssize[x][1] += ssize[y][1]; p[y][1] = x; //adj[a].pb(b); // adj[b].pb(a); cnt++; } if (cnt > 2*n-2) while(true) continue; for (int i = 0; i < n; i++) d[i] = -1; for (int i = 0; i < n; i++) if (d[i] == -1) dfs(i,0,-1); return 0; } /* #include <bits/stdc++.h> using namespace std; #define pb push_back #define sz size const int mxN = 1e5; vector<int> adj[mxN]; //int d[mxN]; //int low[mxN]; int p[mxN][2]; int ss[mxN][2]; void dfs(int c, int depth, int par){ p[c][0] = depth; p[c][1] = depth; int op = par; for (int i : adj[c]){ if (i == par){par = -1; continue;} if (p[i][0] != -1){ p[c][1] = min(p[c][1],p[i][0]); continue;} dfs(i,depth+1,c); p[c][1] = min(p[c][1], p[i][1]); } if (p[c][1]>= depth && op != -1) cout << c+1 << " " << op+1 << '\n'; } int gpar(int c, int w){ if (p[c][w] == c) return c; p[c][w] = gpar(p[c][w],w); return p[c][w]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) {p[i][j] = i; ss[i][j] = 1;} int a,b; int x,y; int cnt = 0; for (int i = 0; i < m; i++){ cin >> a >> b; a -= 1; b -= 1; x = gpar(a,0); y = gpar(b,0); if (x != y){ adj[a].pb(b); adj[b].pb(a); cnt++; if (ss[x][0] < ss[y][0]) swap(x,y); ss[x][0] += ss[y][0]; p[y][0] = x; continue; } cout << x << " 1 " << y << '\n'; x = gpar(a,1); y = gpar(b,1); if (x==y)cout << "Je\n"; if (x == y) continue; cout << x << " " << y << '\n'; if (ss[x][1] < ss[y][1]) swap(x,y); ss[x][1] += ss[y][1]; p[y][1] = x; adj[a].pb(b); adj[b].pb(a); cnt++; } for (int i = 0; i < n; i++) p[i][0] = -1; for (int i = 0; i < n; i++) if (p[i][0] == -1) dfs(i,0,-1); 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...