제출 #171905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171905		dvdg6566	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	310 ms	26804 KiB

oneway

#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 par(int x){return 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;
	for (int i=1;i<=N;++i)if(p[i] == 0){
		p[i] = 1;
		dfs(i,-1);
	}
	memset(out,-1,sizeof(out));
	// 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];
		edges[i].f = a;
		edges[i].s = b;
		if (a == b)continue;
		A[a].pb(b,i);
		A[b].pb(a,i);
		// cout<<a<<' '<<b<<' '<<i<<'\n';
	}
	memset(out,-1,sizeof(out));
	memset(depth,0,sizeof(depth));
	for (int i=1;i<=N;++i)if(depth[i] == 0){
		depth[i]=1;
		d2(i);
	}
	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];
		while (1){
			a = par(a);
			b = par(b);
			// cout<<a<<' '<<b<<'\n';
			if (a == b)break;
			if (depth[a] > depth[b]){
				int target = indextopar[a];
				// cout<<"Set "<<target<<" to "<<a<<'\n';
				out[target] = pp[a];
				// assert(pp[a] == edges[target].f || pp[a] == edges[target].s);
				p[a] = pp[a];
				a = pp[a];
			}else{
				int target = indextopar[b];
				out[target] = b;
				// assert(b == edges[target].f || b == edges[target].s);
				// cout<<"Set "<<target<<" to "<<b<<'\n';
				p[b] = pp[b];
				b = pp[b];
			}
		}
		// cout<<'\n';
	}
	// 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 (edges[i].f == out[i])cout<<"L";
		else if (edges[i].s == out[i])cout<<"R";
		// else assert(0);
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40