oj.uz

답안 #171880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171880 2019-12-30T14:50:53 Z dvdg6566 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 14 ms 10972 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
#define MAXN 101010

vpi V[MAXN];
int N,E,a,b;
int p[MAXN];
int W[MAXN];
stack<int> stk;
int lowlink[MAXN], bcc[MAXN], depth[MAXN];
vpi A[MAXN];
int out[MAXN];
int indextopar[MAXN];
int pp[MAXN];
vpi edges;

void dfs(int x, int w){
	depth[x] = lowlink[x] = a++;
	stk.push(x);
	for (auto i : V[x])if(i.s != w){
		if (p[i.f]){
			lowlink[x] = min(lowlink[x], lowlink[i.f]);
			continue;
		}
		p[i.f] = x;
		dfs(i.f,i.s);
		lowlink[x] = min(lowlink[x], lowlink[i.f]);
	}
	if (lowlink[x] == depth[x]){
		while(stk.top() != x){
			bcc[stk.top()] = b;
			stk.pop();
		}
		stk.pop();
		bcc[x] = b++;
	}
}

void d2(int x){
	for (auto v:A[x])if(v.f != pp[x]){
		pp[v.f] = x;
		depth[v.f] = depth[x]+1;
		indextopar[v.f] = v.s;
		d2(v.f);
	}
}

int par(int x){return (p[x] == x)?x:p[x] = par(p[x]);}

int main(){
	cin>>N>>E;
	for (int i=0;i<E;++i){
		cin>>a>>b;
		V[a].pb(b,i);
		V[b].pb(a,i);
		edges.pb(a,b);
	}
	a=1;b=1;
	p[1] = 1;
	dfs(1,-1);
	// for (int i=1;i<=N;++i)cout<<bcc[i]<<' ';cout<<'\n';
	N = b-1;
	for (int i=0;i<SZ(edges);++i){
		a = bcc[edges[i].f];
		b = bcc[edges[i].s];
		if (a == b){
			out[i] = -1;
			continue;
		}
		A[a].pb(b,i);
		A[b].pb(a,i);
		// cout<<a<<' '<<b<<' '<<i<<'\n';
	}
	memset(depth,0,sizeof(depth));
	depth[1]=1;
	d2(1);
	for (int i=1;i<=N;++i)p[i]=i;
	int Q;
	cin>>Q;
	while(Q--){
		cin>>a>>b;
		a=bcc[a];b=bcc[b];
		if (a == b)continue;
		while (1){
			a = par(a);
			b = par(b);
			if (a == b)break;
			if (depth[a] > depth[b]){
				int target = indextopar[a];
				out[target] = pp[a];
				a = pp[a];
			}else{
				int target = indextopar[b];
				out[target] = b;
				b = pp[b];
			}
		}
	}
	// for (int i=0;i<E;++i)cout<<out[i]<<' ';
	for (int i=0;i<E;++i){
		if (out[i] == -1)cout<<"B";
		else if (bcc[edges[i].f] == out[i])cout<<"L";
		else if (bcc[edges[i].s] == out[i])cout<<"R";
		else assert(0);
	}
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 10972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 10972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 10972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -