Submission #147291

#	Time	Username	Problem	Language	Result	Execution time	Memory
147291		MvC	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	234 ms	30712 KiB

oneway

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,m,i,fin[nmax],fup[nmax],br[nmax],x,y,l,tin,ex[nmax],ey[nmax],par[nmax][20],c[nmax],k,in[nmax],out[nmax],z,up[nmax],dw[nmax];
vector<int>a[nmax];
vector<pair<int,int> >g[nmax];
bitset<nmax>viz;
char rs[nmax];
void dfs(int x,int p=-1)
{
	viz[x]=1;
	fin[x]=fup[x]=++tin;
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==p)continue;
		int y=x^ex[a[x][i]]^ey[a[x][i]];
		if(viz[y])
		{
			fup[x]=min(fup[x],fin[y]);
		}
		else
		{
			dfs(y,a[x][i]);
			fup[x]=min(fup[x],fup[y]);
			if(fup[y]>fin[x])
			{
				br[a[x][i]]=1;
			}
		}
	}
}
void col(int x)
{
	viz[x]=1;
	c[x]=k;
	for(int i=0;i<a[x].size();i++)
	{
		int y=x^ex[a[x][i]]^ey[a[x][i]];
		if(viz[y] || br[a[x][i]])continue;
		col(y);
	}
}
void con(int x)
{
	viz[x]=1;
	for(int i=0;i<a[x].size();i++)
	{
		int y=x^ex[a[x][i]]^ey[a[x][i]];
		if(br[a[x][i]])
		{
			g[c[x]].pb(mkp(c[y],a[x][i]));
			//g[c[y]].pb(c[x]);
			continue;
		}
		if(viz[y])continue;
		con(y);
	}
}
void build(int x,int p)
{
	viz[x]=1;
	par[x][0]=p;
	in[x]=++tin;
	for(int i=1;i<18;i++)par[x][i]=par[par[x][i-1]][i-1];
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i].fr;
		if(y==p)continue;
		build(y,x);
	}
	out[x]=++tin;
}
int anc(int x,int y)
{
	return in[x]<=in[y] && out[y]<=out[x];
}
int lca(int x,int y)
{
	if(anc(x,y))return x;
	if(anc(y,x))return y;
	for(int i=17;i>=0;i--)if(!anc(par[x][i],y))x=par[x][i];
	return par[x][0];
}
void rec(int x,int p,int ed)
{
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i].fr;
		if(y==p)continue;
		rec(y,x,g[x][i].sc);
		up[x]+=up[y];
		dw[x]+=dw[y];
	}
	//cout<<x<<" "<<ed<<"   "<<up[x]<<" "<<dw[x]<<endl;
	if(up[x])
	{
		if(c[ex[ed]]==x)rs[ed]='R';
		else rs[ed]='L';
	}
	if(dw[x])
	{
		if(c[ex[ed]]==x)rs[ed]='L';
		else rs[ed]='R';
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>ex[i]>>ey[i];
		a[ex[i]].pb(i);
		a[ey[i]].pb(i);
	}
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			dfs(i);
		}
	}
	viz.reset();
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			k++;
			col(i);
		}
	}
	viz.reset();
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			con(i);
		}
	}
	viz.reset();
	for(i=1;i<=k;i++)
	{
		if(viz[i])continue;
		build(i,i);
	}
	cin>>z;
	while(z--)
	{
		cin>>x>>y;
		x=c[x],y=c[y];
		l=lca(x,y);
		up[x]++;
		up[l]--;
		dw[y]++;
		dw[l]--;
	}
	viz.reset();
	for(i=1;i<=k;i++)
	{
		if(viz[i])continue;
		rec(i,i,0);
	}
	for(i=1;i<=m;i++)
	{
		if(rs[i]=='L' || rs[i]=='R')cout<<rs[i];
		else cout<<'B';
	}
	cout<<endl;
	return 0;
}

Compilation message (stderr)

oneway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
oneway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void col(int)':
oneway.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void con(int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void build(int, int)':
oneway.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void rec(int, int, int)':
oneway.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~

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