Submission #236630

#	Time	Username	Problem	Language	Result	Execution time	Memory
236630		bharat2002	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	7 ms	5120 KiB

oneway

/*input
7 6
1 2
1 3
2 4
2 5
3 6
3 7
4
4 7
4 3
2 7
6 7
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int N2=20;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int n, m, P;vector< pii > adj[N], adjlist[N];
pii arr[N];int disc[N], low[N], cur, cno[N], p[N][N2], addu[N], addv[N], sub[N],ent[N], ex[N], depth[N];
bool art[N];bool dup[N];string ans;
vector< pii > edges;
void dfs(int i, int p)
{
//	cout<<i<<" ";
	disc[i]=cur++;low[i]=disc[i];
	int ct=0;
	for(auto &j:adj[i])
	{
		if(j.f==p) ct++;
		if(j.f==p) continue;
		if(disc[j.f]==inf)
		{
			dfs(j.f, i);
			if(low[j.f]>disc[i]) art[j.s]=1;
			low[i]=min(low[i], low[j.f]);
		}
		else
		{
			low[i]=disc[j.f];
		}
	}
	if(ct>1)
		for(auto j:adj[i]) 
			if(j.f==p) dup[j.s]=1;
}
void dfs2(int i)
{
	cno[i]=cur;
	for(auto j:adj[i])
	{
		if(art[j.s]) adjlist[cur].push_back(j);
		if(cno[j.f]!=-1||art[j.s]) continue;
		dfs2(j.f);
	}
}
void dfs3(int i)
{
	for(auto j:adjlist[i])
	{
		if(j.f==p[i][0]) continue;
		depth[j.f]=depth[i]+1;
		p[j.f][0]=i;dfs3(j.f);
	}
}
int LCA(int u, int v)
{
	if(depth[u]>depth[v]) swap(u, v);
	int diff=depth[v]-depth[u];
	for(int i=N2-1;i>=0;i--)
	{
		if((1<<i)<=diff)
		{
			diff-=(1<<i);v=p[v][i];
		}
	}
	if(u==v) return u;
	for(int i=N2-1;i>=0;i--)
	{
		if(p[u][i]!=p[v][i]) {u=p[u][i];v=p[v][i];}
	}
	return p[u][0];
}
void dfsf(int i)
{
	int pind;
	for(auto j:adjlist[i])
	{
		if(j.f==p[i][0]) {
			pind=j.s;
			continue;}
		dfsf(j.f);ex[i]+=ex[j.f];ent[i]+=ent[j.f];
	}
	ent[i]-=sub[i];ex[i]-=sub[i];ent[i]+=addv[i];ex[i]+=addu[i];
	if(i==1) return;
	if(ent[i]>0)
	{
		int u=edges[pind].f, v=edges[pind].s;
		u=cno[u];v=cno[v];
		if(v==i) ans[pind]='R';
		else ans[pind]='L';
	}
	else if(ex[i]>0)
	{
		int u=edges[pind].f, v=edges[pind].s;
		u=cno[u];v=cno[v];
		if(v==i) ans[pind]='L';
		else ans[pind]='R';	
	}
	//cout<<i<<": "<<ent[i]<<" "<<ex[i]<<endl;
}
void solve()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		art[i]=0;dup[i]=0;
		int u, v;cin>>u>>v;adj[u].push_back(mp(v, i));adj[v].push_back(mp(u, i));edges.push_back(mp(u, v));
	}
	cin>>P;
	for(int i=0;i<m;i++) ans.push_back('B');
	for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
	for(int i=1;i<=n;i++) {disc[i]=inf;cno[i]=-1;addu[i]=addv[i]=ent[i]=ex[i]=0;}
	cur=1;
	dfs(1, 1);
	for(int i=0;i<m;i++) 
	if(dup[i]) art[i]=0;cur=1;
	for(int i=1;i<=n;i++)
	{
		if(cno[i]==-1) {dfs2(i);cur++;}
	}
	for(int i=1;i<cur;i++)
		for(auto &j:adjlist[i]) j.f=cno[j.f];
	cur--;p[1][0]=1;depth[1]=0;
/*	for(int i=1;i<=cur;i++)
	{
		cout<<i<<": ";
		for(auto j:adjlist[i]) cout<<j.f<<" "<<j.s<<endl;
	}*/
	dfs3(1);
	for(int j=1;j<N2;j++)
		for(int i=1;i<=n;i++) p[i][j]=p[p[i][j-1]][j-1];
	for(int j=1;j<=P;j++)
	{
		pii i=arr[j];
		i.f=cno[i.f], i.s=cno[i.s];
		addu[i.f]++;addv[i.s]++;
		int u=LCA(i.f, i.s);
//		cout<<i.f<<" "<<i.s<<" -"<<u<<endl;
		sub[u]++;
	}
	dfsf(1);
	cout<<ans;
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t=1;
	while(t--)
	{
		solve();
	}
}

Compilation message (stderr)

oneway.cpp: In function 'void solve()':
oneway.cpp:132:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
  ^~~
oneway.cpp:132:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
                                                ^~~
oneway.cpp:137:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(dup[i]) art[i]=0;cur=1;
  ^~
oneway.cpp:137:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(dup[i]) art[i]=0;cur=1;
                      ^~~
oneway.cpp:136:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=0;i<m;i++) 
  ^~~
oneway.cpp:137:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  if(dup[i]) art[i]=0;cur=1;
                      ^~~
oneway.cpp: In function 'void dfsf(long long int)':
oneway.cpp:108:19: warning: 'pind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int u=edges[pind].f, v=edges[pind].s;
                   ^

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