oj.uz

답안 #527434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527434 2022-02-17T11:49:34 Z zaneyu Pipes (CEOI15_pipes) C++14
100 / 100
 379 ms 14672 KB 
/*input
10 12
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
10 9
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
} 
/** Interface */

inline int readChar();
template <class T = int> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );

/** Read */

static const int buf_size = 4096;

inline int getChar() {
	static char buf[buf_size];
	static int len = 0, pos = 0;
	if (pos == len)
		pos = 0, len = fread(buf, 1, buf_size, stdin);
	if (pos == len)
		return -1;
	return buf[pos++];
}

inline int readChar() {
	int c = getChar();
	while (c <= 32)
		c = getChar();
	return c;
}

template <class T>
inline T readInt() {
	int s = 1, c = readChar();
	T x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar( int x ) {
	if (write_pos == buf_size)
		fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
	write_buf[write_pos++] = x;
}

template <class T> 
inline void writeInt( T x, char end ) {
	if (x < 0)
		writeChar('-'), x = -x;

	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
	if (end)
		writeChar(end);
}

inline void writeWord( const char *s ) {
	while (*s)
		writeChar(*s++);
}

struct Flusher {
	~Flusher() {
		if (write_pos)
			fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
	}
} flusher;
struct ufds{
	int par[maxn];
	void init(int n){
		REP(i,n) par[i]=i;
	}
	inline int find(int u){
		if(par[u]==u) return u;
		return par[u]=find(par[u]);
	}
	inline void merge(int a,int b){
		a=find(a),b=find(b);
		par[a]=b;
	}
}u1,u2;
int low[maxn],depth[maxn];
vector<int> v[maxn];
int cur=0;
inline void dfs(int u,int p){
   low[u]=depth[u]=++cur;
   bool hv=0;
   for(auto x:v[u]){
   		if(x==p and !hv){
   			hv=1;
   			continue;
   		}
       if(!depth[x]){
          dfs(x,u);
          MNTO(low[u],low[x]);
          if(low[x]>depth[u]){
          	 cout<<u+1<<' '<<x+1<<'\n';
          }
          //check AP low[x]>=depth[u],bridge >
          //doesnt work for multiedges 
       }
       else{
           low[u]=min(low[u],depth[x]);
       }
   }
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int n=readInt(),m=readInt();
	vector<pii> ed;
	u1.init(n),u2.init(n);
	REP(i,m){
		int a=readInt(),b=readInt();
		--a,--b;
		if(u1.find(a)!=u1.find(b)){
			u1.merge(a,b);
			v[a].pb(b);
			v[b].pb(a);
		}
		else if(u2.find(a)!=u2.find(b)){
			u2.merge(a,b);
			v[a].pb(b);
			v[b].pb(a);
		}
	}
	REP(i,n){
		if(!depth[i]) dfs(i,-1);
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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