Submission #116715

#TimeUsernameProblemLanguageResultExecution timeMemory
116715JohnTitorPipes (CEOI15_pipes)C++14
100 / 100
709 ms15468 KiB
#include <vector> #include <algorithm> #include <stdio.h> #include <locale> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; //mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Pipes" class dsu{ public: int n; vector <int> r; vector <pair <int, int>> edges; void reset(int n){ this->n=n; r.resize(n+1); FOR(i, 1, n) r[i]=-1; edges.clear(); } int root(int u){ if(r[u]<0) return u; return r[u]=root(r[u]); } bool unite(int u, int v){ int ou=u; int ov=v; u=root(u); v=root(v); if(u==v) return 0; edges.pb(mp(ou, ov)); if(r[u]>r[v]) swap(u, v); r[u]+=r[v]; r[v]=u; return 1; } } d[2]; int n, m; vector <int> g[100001]; vector <bool> done; int cnt=0; vector <int> low; vector <int> num; vector <int> p; void dfs(int u){ done[u]=1; cnt++; num[u]=low[u]=cnt; for(auto &x: g[u]) if(x==p[u]){ swap(x, g[u].back()); g[u].pop_back(); break; } for(int &v: g[u]) if(!done[v]){ p[v]=u; dfs(v); low[u]=min(low[u], low[v]); } else low[u]=min(low[u], num[v]); for(int &v: g[u]) if(p[v]==u){ if(low[v]>num[u]){ write(u); putchar(' '); writeln(v); } p[v]=0; } } int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); read(m); d[0].reset(n); d[1].reset(n); { int u, v; FOR(i, 1, m){ read(u); read(v); if(!d[0].unite(u, v)) d[1].unite(u, v); } } FOR(b, 0, 1){ while(!d[b].edges.empty()){ auto p=d[b].edges.back(); d[b].edges.pop_back(); g[p.first].pb(p.second); g[p.second].pb(p.first); } d[b].r.clear(); } done.resize(n+1, 0); num.resize(n+1, 0); low.resize(n+1, 0); p.resize(n+1, 0); FOR(i, 1, n) if(!done[i]) dfs(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...