Submission #63155

#	Time	Username	Problem	Language	Result	Execution time	Memory
63155		khsoo01	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	219 ms	44988 KiB

oneway

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 100005;

int n, m, q, ans[N], dep[N], p[N], dir[N];
bool vis[N], bc[N];

vector<int> adj[N];
vector<pii> edg;

struct disj {
	int par[N];
	void init () {iota(par, par+n+1, 0);}
	int Find (int X) {
		if(par[X] == X) return X;
		return par[X] = Find(par[X]);
	}
	void Union (int A, int B) {
		A = Find(A); B = Find(B);
		if(A == B) return;
		par[A] = B;
	}
} uf;

void calc (int C, int P) {
	if(vis[C]) return;
	vis[C] = true;
	dep[C] = dep[P] + 1;
	p[C] = P;
	for(auto &T : adj[C]) calc(T, C);
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		edg.push_back({A, B});
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	for(int i=1;i<=n;i++) {
		if(!vis[i]) calc(i, 0);
	}
	uf.init();
	scanf("%d",&q);
	for(int i=1;i<=q;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		while(uf.Find(A) != uf.Find(B)) {
			A = uf.Find(A); B = uf.Find(B);
			if(dep[A] > dep[B]) {
				dir[A] = 1;
				uf.Union(A, p[A]);
			}
			else {
				dir[B] = 2;
				uf.Union(B, p[B]);
			}
		}
	}
	uf.init();
	fill(vis+1, vis+1+n, false);
	for(int i=1;i<=n;i++) {
		bool flag = false;
		for(auto &T : adj[i]) {
			if(!flag && T == p[i]) {
				flag = true; continue;
			}
			while(dep[uf.Find(i)] > dep[T]) {
				int I = uf.Find(i);
				bc[I] = true;
				uf.Union(I, p[I]);
			}
		}
	}
	for(int i=0;i<m;i++) {
		if(p[edg[i].X] == edg[i].Y) {
			int I = edg[i].X;
			if(bc[I] || !dir[I]) printf("B");
			else if(dir[I] == 1) printf("R");
			else printf("L");
		}
		else if(p[edg[i].Y] == edg[i].X) {
			int I = edg[i].Y;
			if(bc[I] || !dir[I]) printf("B");
			else if(dir[I] == 1) printf("L");
			else printf("R");
		}
		else printf("B");
	}
	puts("");
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
oneway.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~
oneway.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
oneway.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~

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