Submission #1370830

#TimeUsernameProblemLanguageResultExecution timeMemory
1370830lamnxOne-Way Streets (CEOI17_oneway)C++17
0 / 100
2 ms4932 KiB
#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define	 all(a)				a.begin(), a.end()
#define	 pb					push_back
#define	 pf					push_front
#define	 fi					first
#define	 se					second
#define	 int				   long long
#define	 F(i,k,n)			  for(int i=k;i<=n;i++)

typedef	 long long			 ll;
typedef	 unsigned long long	ull;
typedef	 double				db;
typedef	 long double		   ld;
typedef	 pair<db, db>		  pdb;
typedef	 pair<ld, ld>		  pld;
typedef	 pair<int, int>		pii;
typedef	 pair<ll, ll>		  pll;
typedef	 pair<ll, int>		 plli;
typedef	 pair<int, ll>		 pill;

const int N = 1e5+67;
const int LOG=20;
struct Edge
{
	int u,v,id;
	Edge(){}
	Edge(int _u,int _v,int _id)
	{
		u=_u;
		v=_v;
		id=_id;
	}
};
vector<Edge>e;
int n,m,p;
vector<int>adj[N];
vector<pii>a[N];
int tin[N],low[N];
int comp[N],cnt=0;
bool is_bridge[N];
int timer=0;
void dfs_find_bridge(int u,int p)
{
	tin[u]=low[u]=++timer;
	for(auto &[v,id]:a[u]) if(id!=p)
	{
		if(!tin[v])
		{
			dfs_find_bridge(v,id);
			low[u]=min(low[u],low[v]);
			if(low[v]>tin[u])
			{
				is_bridge[id]=1;
			}
		}
		else
		{
			low[u]=min(low[u],tin[v]);
		}
	}
}
void init()
{
	cin>>n>>m;
	F(i,1,m)
	{
		int u,v;
		cin>>u>>v;
		a[u].pb({v,i});
		a[v].pb({u,i});
		e.pb(Edge(u,v,i));
	}
	F(i,1,n)
	{
		if(!tin[i])
		{
			dfs_find_bridge(i,0);
		}
	}
}
void dfs_build_tree(int u,int cnt)
{
	comp[u]=cnt;
	for(auto &[v,id]:a[u]) if(!is_bridge[id] and !comp[v])
	{
		dfs_build_tree(v,cnt);
	}
}
void build_bridge_tree()
{
	F(i,1,n)
	{
		if(!comp[i])
		{
			dfs_build_tree(i,++cnt);
		}
	}
	for(auto [u,v,id]:e)
	{
		if(comp[u]==comp[v])continue;
		adj[comp[u]].pb(comp[v]);
		adj[comp[v]].pb(comp[u]);
	}
}
int nxt[N][LOG];
int d[N];
void dfs_lca(int u,int p)
{
	nxt[u][0]=p;
	d[u]=d[p]+1;
	for(auto &v:adj[u]) if(v!=p)
	{
		dfs_lca(v,u);
	}
	return;
}
void build_lca()
{
	dfs_lca(1,0);
	for(int j=1;j<LOG;j++) for(int i=1;i<=cnt;i++)
	{
		nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	}
}
int getlca(int u,int v)
{
	if(d[u]<d[v])swap(u,v);
	for(int i=LOG-1;i>=0;i--) if(d[nxt[u][i]]>=d[v])
	{
		u=nxt[u][i];
	}
	if(u==v)return u;
	for(int i=LOG-1;i>=0;i--) if(nxt[u][i]!=nxt[v][i])
	{
		u=nxt[u][i];
		v=nxt[v][i];
	}
	return nxt[u][0];
}
int up[N],down[N];
void query(int u,int v)
{
	u=comp[u];
	v=comp[v];
	int lca=getlca(u,v);
	up[lca]--;
	up[u]++;
	down[lca]--;
	down[v]++;
}
void dfs_ans(int u,int p)
{
	for(auto &v:adj[u]) if(v!=p)
	{
		dfs_ans(v,u);
		up[u]+=up[v];
		down[u]+=down[v];
	}
}
void get_ans()
{
	dfs_ans(1,0);
	for(auto [u,v,id]:e)
	{
		u=comp[u];
		v=comp[v];
		if(u==v)
		{
			cout<<'B';
			continue;
		}
		bool doi=(d[u]<d[v]);
		if(doi)swap(u,v);
		if(up[u] && down[u])
		{
			cout<<'B';
		}
		else if(up[u])
		{
			if(doi) cout<<'L';
			else cout<<'R';
		}
		else{
			if(doi)cout<<'R';
			else cout<<'L';
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen(".inp","r",stdin); freopen(".out","w",stdout);
	init();
	build_bridge_tree();
	build_lca();
	cin>>p;
	F(i,1,p)
	{
		int u,v;
		cin>>u>>v;
		query(u,v);
	}
	get_ans();
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...