Submission #668753

#TimeUsernameProblemLanguageResultExecution timeMemory
668753KiaRezPipes (CEOI15_pipes)C++17
80 / 100
1028 ms16884 KiB
/* IN THE NAME OF GOD ........................................................................................................................... ........................................................................................................................... .......@..........@....@@@@@@@@@............@..............@@@@@@@@@@........@@@@@@@@@@@.......@@@@@@@@@@@@@@@@@........... .......@........@..........@...............@.@.............@........@........@................................@............ .......@......@............@..............@...@............@........@........@..............................@.............. .......@....@..............@.............@.....@...........@........@........@............................@................ .......@..@................@............@.......@..........@@@@@@@@@@........@..........................@.................. .......@.@.................@...........@@@@@@@@@@@.........@...@.............@@@@@@@@@@@..............@.................... .......@....@..............@..........@...........@........@....@............@......................@...................... .......@.......@...........@.........@.............@.......@.....@...........@....................@........................ .......@.........@.........@........@...............@......@......@..........@..................@.......................... .......@...........@...@@@@@@@@@...@.................@.....@.......@.........@@@@@@@@@@@@......@@@@@@@@@@@@@@@............. ........................................................................................................................... ........................................................................................................................... */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef pair<int, pii> ipii; typedef pair<pii, int> piii; typedef pair<ll, pll> lpll; typedef pair<pll, ll> plll; typedef pair<pii, pii> piipii; typedef pair<pll, pll> pllpll; typedef long double ld; #define SP ' ' #define endl '\n' #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define DASH "---------" #define UNDERLINE "_________" #define all(x) (x).begin(),(x).end() #define FORD(i, s, e) for(int i=s; i>=e; --i) #define FOR(i, s, e) for(int i=s; i<=e; ++i) #define kill(x) cout << x << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define fuck(x) cout << #x << " : " << x << endl #define ios ios_base::sync_with_stdio(false), cin.tie(0) #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); const int N = 1e5+10; const ll MOD = 1e9+7; ll getmod(ll a, ll mod=MOD) {return (a+mod)%mod;} ll max(ll a, ll b) {return (a>b ? a : b);} ll min(ll a, ll b) {return (a<b ? a : b);} ll abso(ll a) {return (a<0?-a:a);} int n, par[N][2], m, low[N], lay[N], ind2; bool mark[N]; vector<pii> adj[N]; int getPar(int v, int ind) {int tmpv=v; while(par[v][ind]!=0) {v=par[v][ind];} while(par[tmpv][ind]!=0) {int fck=tmpv; tmpv=par[tmpv][ind]; par[fck][ind]=v;} return v;} void update(int v, int u, int ind) {v=getPar(v, ind), u=getPar(u, ind);if (v==u){return;}par[v][ind]=u;} void dfs(int v, int index){ mark[v]=1, lay[v]=lay[par[v][0]]+1; for(auto it : adj[v]) { if (!mark[it.F]) {par[it.F][0]=v; dfs(it.F, it.S); low[v]=min(low[v], low[it.F]);} else if (mark[it.F] && it.S!=index) {low[v]=min(low[v], lay[it.F]);} } if (low[v] > lay[par[v][0]] && par[v][0]!=0) {cout << min(v, par[v][0]) << ' ' << max(v, par[v][0]) << endl;} } int main () { ios; cin>>n>>m; fill(low, low+n+5, 1e9); FOR(i, 1, m){ int v, u;cin>>v>>u; if (getPar(v, 0) != getPar(u, 0)) {update(v, u, 0); adj[v].pb({u, ++ind2}); adj[u].pb({v, ind2});} else if (getPar(v, 1) != getPar(u, 1)) {update(v, u, 1); adj[v].pb({u, ++ind2}); adj[u].pb({v, ind2});} } FOR(i, 0, n+2) {par[i][0]=0;} FOR(i, 1, n) {if (!mark[i]) {dfs(i, 0);}} 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...