Submission #1280005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280005		WH8	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	178 ms	35564 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
signed main(){
	int n,m;cin>>n>>m;
	vector<vector<pair<int,int>>> al(n+1);
	vector<int> ord(n+1, -1), low(n+1, 1e9), out(n+1);
	vector<array<int, 2>> ed(m+1);
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		ed[i][0]=a, ed[i][1]=b;
		al[a].pb({i, 1});
		al[b].pb({i, 0});
	}
	int q; cin >> q;
	int t=0;
	vector<vector<pair<int,int>>> ep(n+1);
	vector<pair<int,int>> mn(n+1, {1e9, 0}), mx(n+1, {-1, 0});
	for(int i=0;i<q;i++){
		int a, b;cin>>a>>b;
		ep[a].pb({b, 1ll});
		ep[b].pb({a, 0ll});
	}
	auto dfs1 = [&](auto self, int x, int p) -> void{
		ord[x]=low[x]=t;
		t++;
		//~ cout<<x<<" " << t<<endl;
		for(auto [e, d]:al[x]){
			if(e==p)continue;
			if(ord[ed[e][d]] != -1)low[x]=min(low[x], ord[ed[e][d]]);
			else {
				self(self, ed[e][d], e);
				low[x]=min(low[x], low[ed[e][d]]);
			}
		}
		//~ cout<<x<<" " << t<<endl;

		out[x]=t-1;
	};
	for(int i=1;i<=n;i++) if(ord[i]==-1)dfs1(dfs1, i, m);
	//~ return 0;
	vector<bool> vis(n+1, 0);
	vector<int> ans(m+1, -1);
	auto dfs2 = [&](auto dfs2, int x, int p) -> void{ // p is parent edge, 
		vis[x]=true;
		bool up=false;
		if(p!=m) up=(ed[p][0]==x);
		//~ if(x!=1 and ed[p][0]!=x and ed[p][1]!=x)assert(false);
		for(auto [point, dir] : ep[x]){
			//~ printf("%lld : point %lld dir %lld , ord %lld\n", x, point,dir,ord[point]);
			mn[x]=min(mn[x], mp(ord[point], dir));
			mx[x]=max(mx[x], mp(ord[point], dir));
		}
		for(auto [e, i] : al[x]){
			int to=ed[e][i];
			if(vis[ed[e][i]])continue;
			dfs2(dfs2,to, e);
			mn[x]=min(mn[x], mn[to]);
			mx[x]=max(mx[x], mx[to]);
		}
				//~ printf("at %lld parent edge index %lld, ord %lld, out %lld, low %lld\n", x, p, ord[x], out[x], low[x]); 
		//~ printf("mn %lld %lld, mx %lld %lld\n", mn[x].f, mn[x].s, mx[x].f,mx[x].s);
		//~ fflush(stdout);
		if(low[x] < ord[x])ans[p]=-1;
		else {

			if(mn[x].f < ord[x]){
				ans[p]=(up == mn[x].s);
			}
			else if(mx[x].f > out[x]){
				ans[p]=(up == mx[x].s);
			}
			else {
				ans[p]=-1;
			}
		}
	};

	for(int i=1;i<=n;i++) if (!vis[i]) dfs2(dfs2, i, m);
	
	for(int i=0;i<m;i++){
		//~ cout<<ans[i]<<endl;
		if(ans[i]==0)cout<<'L';
		else if (ans[i]==1)cout<<'R';
		else cout<<'B';
		//~ else assert(false);
	}
}
/*
5 4
1 2
3 2 
3 4
4 5 
2
1 4
5 4
*/
/*
7 6
1 2
2 3
2 4
1 5
5 6
5 7
2
6 2 
4 3 

*/

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