Submission #1222346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222346		Nika533	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	742 ms	85096 KiB

oneway

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,m,T,k,q,fix[N],depth[N],anc[N][20],d[N],val[N],big=1e9,dp[N],fix2[N],fix3[N];
map<pii,int> mymap,mymap2;
vector<int> g[N];
vector<pair<int,pii>> e[N];
vector<pii> br;
map<pii,pii> ne;

void dfs(int x, int p) {
	fix[x]=1;
	depth[x]=depth[p]+1;
	int up=0,down=0;
	for (auto y:g[x]) {
		if (fix[y]) {
			if (depth[x]>depth[y]) up++;
			else down++;
			continue;
		}
		dfs(y,x); dp[x]+=dp[y];
	}
	if (x==1) up++;
	dp[x]+=(up-1)-down;
//	cout<<"XP "<<x<<" "<<p<<" "<<dp[x]<<endl;
	if (x!=1 && dp[x]==0) {
		br.pb({x,p});
		mymap2[{x,p}]=mymap2[{p,x}]=1;
	}
}

int p[N],sz[N];
void make_set(int v) {
	sz[v]=1; p[v]=v;
}
int find_set(int v) {
	if (p[v]==v) return v;
	return p[v]=find_set(p[v]);
}
void merge_set(int a, int b) {
	a=find_set(a); b=find_set(b);
	if (a==b) return;
	if (sz[a]<sz[b]) swap(a,b);
	p[b]=a; sz[a]+=sz[b];
}

int ancestor(int a, int b) {
	int res=a;
	for (int j=0; j<20; j++) {
		if (b&(1<<j)) res=anc[res][j];
	}
	return res;
}

int LCA(int a, int b) {
	if (d[a]>d[b]) {
		a=ancestor(a,d[a]-d[b]);
	}
	else if (d[b]>d[a]) {
		b=ancestor(b,d[b]-d[a]);
	}
	if (a==b) return a;
	for (int j=19; j>=0; j--) {
		if (anc[a][j]!=anc[b][j]) {
			a=anc[a][j]; b=anc[b][j];
		}
	}
	return anc[a][0];
}

void dfs0(int x, int p) {
	fix2[x]=1;
	anc[x][0]=p; d[x]=d[p]+1;
	for (auto A:e[x]) {
		int y=A.f;
		if (y==p) continue;
		dfs0(y,x);
	}
}


string s;
void solve(int x, int p) {
	for (auto A:e[x]) {
		int y=A.f;
		if (y==p) continue;
		solve(y,x); val[x]+=val[y];
	}
	if (p==0) return;
	if (val[x]==0) return; int VAL=val[x];
	int xx=ne[{x,p}].f,yy=ne[{x,p}].s;
//	cout<<"XXX "<<x<<" "<<val[x]<<" "<<xx<<" "<<yy<<endl;
	x=xx,p=yy; 
	if (VAL<big) {
		if (mymap[{x,p}]) {
			s[mymap[{x,p}]-1]='R';
		}
		else {
			s[mymap[{p,x}]-1]='L';
		}
	}
	else {
		if (mymap[{x,p}]) {
			s[mymap[{x,p}]-1]='L';
		}
		else {
			s[mymap[{p,x}]-1]='R';
		}
	}
}


void test_case() {
	cin>>n>>m;
	for (int i=1; i<=m; i++) {
		s.pb('B');
		int a,b; cin>>a>>b;
		if (a==b) continue;
		g[a].pb(b); g[b].pb(a);
		mymap[{a,b}]=i;
	}
	for (int i=1; i<=n; i++) {
		if (fix[i]==0) dfs(i,0);
	}
	for (int i=1; i<=n; i++) make_set(i);
	for (int i=1; i<=n; i++) {
		for (auto j:g[i]) {
			if (mymap2[{i,j}]) continue;
			merge_set(i,j);
		}
	}
	
	for (auto A:br) {
		int x=A.f,y=A.s;
		int xx=x; int yy=y;
		x=find_set(x); y=find_set(y);
//		cout<<x<<" "<<y<<endl;
		ne[{x,y}]={xx,yy};
		ne[{y,x}]={yy,xx};
		e[x].pb({y,{xx,yy}}); e[y].pb({x,{yy,xx}});
	}
	
	for (int i=1; i<=n; i++) {
		if (fix2[find_set(i)]==0) {
			dfs0(find_set(i),0);
			fix3[i]=1;
//			cout<<"F3 "<<i<<" "<<find_set(i)<<endl;
		}
	}
	for (int j=1; j<20; j++) {
		for (int i=1; i<=n; i++) {
			anc[i][j]=anc[anc[i][j-1]][j-1];
		}
	}
	
	cin>>q;
	while (q--) {
		int a,b; cin>>a>>b;
		a=find_set(a); b=find_set(b);
		int c=LCA(a,b);
//		cout<<a<<" "<<b<<" "<<c<<endl;
		val[a]+=1; val[c]-=1; val[b]+=big; val[c]-=big;
	}
	
	for (int i=1; i<=n; i++) {
		if (fix3[i]==1) solve(find_set(i),0);
	}
	cout<<s<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; 
	while (T--) test_case();
}

Compilation message (stderr)

oneway.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
oneway.cpp:180:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  180 | main () {
      | ^~~~

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