oj.uz

답안 #171904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171904 2019-12-30T15:21:35 Z dvdg6566 One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 23656 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 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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 8 ms 6008 KB Output is correct
4 Correct 8 ms 6008 KB Output is correct
5 Correct 8 ms 6008 KB Output is correct
6 Correct 8 ms 6008 KB Output is correct
7 Correct 8 ms 6008 KB Output is correct
8 Correct 8 ms 6008 KB Output is correct
9 Correct 8 ms 6008 KB Output is correct
10 Correct 8 ms 6008 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 8 ms 6008 KB Output is correct
4 Correct 8 ms 6008 KB Output is correct
5 Correct 8 ms 6008 KB Output is correct
6 Correct 8 ms 6008 KB Output is correct
7 Correct 8 ms 6008 KB Output is correct
8 Correct 8 ms 6008 KB Output is correct
9 Correct 8 ms 6008 KB Output is correct
10 Correct 8 ms 6008 KB Output is correct
11 Correct 143 ms 15116 KB Output is correct
12 Correct 159 ms 16240 KB Output is correct
13 Correct 166 ms 17140 KB Output is correct
14 Correct 180 ms 18152 KB Output is correct
15 Correct 180 ms 18824 KB Output is correct
16 Correct 247 ms 21076 KB Output is correct
17 Correct 192 ms 22556 KB Output is correct
18 Correct 213 ms 21128 KB Output is correct
19 Correct 194 ms 23656 KB Output is correct
20 Correct 151 ms 15560 KB Output is correct
21 Correct 144 ms 15204 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 8 ms 6008 KB Output is correct
4 Correct 8 ms 6008 KB Output is correct
5 Correct 8 ms 6008 KB Output is correct
6 Correct 8 ms 6008 KB Output is correct
7 Correct 8 ms 6008 KB Output is correct
8 Correct 8 ms 6008 KB Output is correct
9 Correct 8 ms 6008 KB Output is correct
10 Correct 8 ms 6008 KB Output is correct
11 Correct 143 ms 15116 KB Output is correct
12 Correct 159 ms 16240 KB Output is correct
13 Correct 166 ms 17140 KB Output is correct
14 Correct 180 ms 18152 KB Output is correct
15 Correct 180 ms 18824 KB Output is correct
16 Correct 247 ms 21076 KB Output is correct
17 Correct 192 ms 22556 KB Output is correct
18 Correct 213 ms 21128 KB Output is correct
19 Correct 194 ms 23656 KB Output is correct
20 Correct 151 ms 15560 KB Output is correct
21 Correct 144 ms 15204 KB Output is correct
22 Execution timed out 3030 ms 22948 KB Time limit exceeded
23 Halted 0 ms 0 KB -