Submission #49116

#	Time	Username	Problem	Language	Result	Execution time	Memory
49116		tmwilliamlin168	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	190 ms	19692 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define getchar_unlocked getchar
#define putchar_unlocked putchar

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}

const int mxN=1e5;
int n, m, k, a[mxN], b[mxN], ab[mxN], d[mxN], s[mxN], p[mxN], r[mxN], dt=1, tin[mxN], low[mxN];
bool bg[mxN];
vector<int> adj1[mxN], adj2[mxN];

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

inline void join(int x, int y) {
	if((x=find(x))==(y=find(y)))
		return;
	if(r[x]<r[y])
		p[x]=y;
	else
		p[y]=x;
	if(r[x]==r[y])
		++r[x];
}

void dfs1(int u, int p) {
	tin[u]=low[u]=dt++;
	for(int e : adj1[u]) {
		int v=u^ab[e];
		if(!tin[v]) {
			dfs1(v, e);
			low[u]=min(low[v], low[u]);
			if(low[v]>tin[u])
				bg[e]=1;
		} else if(e!=p)
			low[u]=min(tin[v], low[u]);
	}
}

void dfs2(int u, int p) {
	for(int e : adj2[u]) {
		int v=u^ab[e];
		if(v==p)
			continue;
		d[v]=d[u]+1;
		dfs2(v, u);
		s[u]+=s[v];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	n=in(), m=in();
	for(int i=0; i<n; ++i)
		p[i]=i;
	for(int i=0; i<m; ++i) {
		a[i]=in()-1, b[i]=in()-1;
		ab[i]=a[i]^b[i];
		adj1[a[i]].push_back(i);
		adj1[b[i]].push_back(i);
	}
	for(int i=0; i<n; ++i)
		if(!tin[i])
			dfs1(i, -1);
	for(int i=0; i<m; ++i)
		if(!bg[i])
			join(a[i], b[i]);
	for(int i=0; i<m; ++i) {
		if(!bg[i])
			continue;
		a[i]=find(a[i]);
		b[i]=find(b[i]);
		ab[i]=a[i]^b[i];
		adj2[a[i]].push_back(i);
		adj2[b[i]].push_back(i);
	}
	k=in();
	while(k--)
		++s[find(in()-1)], --s[find(in()-1)];
	for(int i=0; i<n; ++i) {
		if(p[i]==i&&!d[i]) {
			d[i]=1;
			dfs2(i, -1);
		}
	}
	for(int i=0; i<m; ++i) {
		if(!bg[i]) {
			putchar_unlocked('B');
			continue;
		}
		int u=d[a[i]]>d[b[i]]?a[i]:b[i];
		putchar_unlocked(s[u]?((s[u]>0)==(u==a[i])?'R':'L'):'B');
	}
}

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