oj.uz

답안 #668740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668740 2022-12-04T20:41:39 Z KiaRez Pipes (CEOI15_pipes) C++17
70 / 100
 1338 ms 18828 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], mark[N], ind, sz[N][2];
vector<pii> adj[N];

int getPar(int v, int ind) {while(par[v][ind]!=0) {v=par[v][ind];} 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);}par[v][ind]=u;sz[u][ind]+=sz[v][ind];}

void dfs(int v, int l, int p, int index){
	mark[v]=1, lay[v]=l;
	for(auto it : adj[v]) {
		if (!mark[it.F]) {dfs(it.F, l+1, 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, ++ind}); adj[u].pb({v, ind});}
		else if (getPar(v, 1) != getPar(u, 1)) {update(v, u, 1); adj[v].pb({u, ++ind}); adj[u].pb({v, ind});}
	}

	FOR(i, 1, n) {if (!mark[i]) {dfs(i, 1, 0, 0);}}

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3336 KB Output is correct
2 Correct 4 ms 3028 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 3228 KB Output is correct
2 Correct 101 ms 2960 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 4232 KB Output is correct
2 Correct 217 ms 3836 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 294 ms 6232 KB Output is correct
2 Correct 287 ms 6476 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 450 ms 13700 KB Output is correct
2 Correct 354 ms 9484 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 671 ms 15984 KB Output is correct
2 Correct 627 ms 11824 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 888 ms 18828 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1081 ms 18772 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1338 ms 18092 KB Memory limit exceeded
2 Halted 0 ms 0 KB -