Submission #1020341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020341		idiotcomputer	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	44 ms	14672 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define sz size
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second

const int mxN = 1e5+5;
vector<pii> adj[mxN];
int d[mxN];
int low[mxN];
char res[mxN];
int val[mxN];

void dfs(int c, int depth, int pidx){
	d[c] = depth;
	low[c] = depth;

	for (pii i : adj[c]){
		if (i.s == -1*pidx) continue;
		if (d[i.f] != -1){ low[c] = min(low[c],low[i.f]); res[abs(i.s)] = 'B'; continue;}
		dfs(i.f,depth+1,i.s);
		low[c] = min(low[c],low[i.f]);
		val[c] += val[i.f];
	}
	
	//cout << c << " " << low[c] << " " << d[c] << "\n";
	if (pidx == INT_MAX) return;
	if (low[c] < d[c] || val[c] == 0) res[abs(pidx)] = 'B';
	else if (val[c] < 0){
		if (pidx > 0) res[abs(pidx)] = 'R';
		else res[abs(pidx)] = 'L';
	} else {
		if (pidx > 0) res[abs(pidx)] = 'L';
		else res[abs(pidx)] = 'R';
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin >> n >> m;

	int a,b;
	for (int i =0; i < m; i++){
		cin >> a >> b;
		a -= 1;
		b -= 1;
		adj[a].pb((pii) {b,i+1});
		adj[b].pb((pii) {a,-1*i-1});
	}	

	int p;
	cin >> p;
	memset(val,0,sizeof(val));
	for (int i =0; i < p; i++){
		cin >> a >> b;
		a -= 1;
		b -= 1;
		val[a]++;
		val[b]--;
	}

	for (int i = 0; i < n; i++) d[i] = -1;
	for (int i = 0; i < n; i++) if (d[i] == -1) dfs(i,0,INT_MAX);
	
	for (int i = 1; i <= m; i++) cout << res[i];
	cout << '\n';

	return 0;
}

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