| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 668751 |
2022-12-04T21:26:42 Z |
KiaRez |
Pipes (CEOI15_pipes) |
C++14 |
|
918 ms |
17100 KB |
/*
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;//, sz[N][2];
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;}/*if (sz[v][ind]>sz[u][ind]) {swap(v, u);}sz[u][ind]+=sz[v][ind];*/par[v][ind]=u;}
void dfs(int v, int p, int index){
mark[v]=1, lay[v]=lay[p]+1;
for(auto it : adj[v]) {
if (!mark[it.F]) {dfs(it.F, v, 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[p] && p!=0) {cout << min(v, p) << ' ' << max(v, p) << endl;}
}
int main () {
ios;
cin>>n>>m; fill(low, low+n+5, 1e9);// fill(sz[0], sz[0]+n+5, 1); fill(sz[1], sz[1]+n+5, 1);
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, 1, n) {if (!mark[i]) {dfs(i, 0, 0);}}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3284 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
3060 KB |
Output is correct |
| 2 |
Correct |
76 ms |
2928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
4032 KB |
Output is correct |
| 2 |
Correct |
153 ms |
3492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
5964 KB |
Output is correct |
| 2 |
Correct |
190 ms |
5348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
12796 KB |
Output is correct |
| 2 |
Correct |
275 ms |
8716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
474 ms |
14220 KB |
Output is correct |
| 2 |
Correct |
442 ms |
10156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
644 ms |
16976 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
771 ms |
17100 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
918 ms |
16232 KB |
Output is correct |
| 2 |
Correct |
848 ms |
12108 KB |
Output is correct |
