Submission #121885

#	Time	Username	Problem	Language	Result	Execution time	Memory
121885		MvC	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	485 ms	262144 KiB

oneway

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "rail.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<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int i,n,m,x,y,fin[nmax],fup[nmax],tim,viz[nmax],vl[nmax],val[nmax],k,nr,vb[nmax],up[nmax][20],tin[nmax],tout[nmax],t,l,r,j,var[nmax],pr[nmax],e[nmax];
char rs[nmax];
pair<int,int>edg[nmax];
vector<pair<int,int> >a[nmax],gr[nmax];
vector<int>brg,vc,q[nmax];
void dfs(int x,int p)
{
    viz[x]=1;
    fin[x]=fup[x]=tim++;
    for(int i=0;i<a[x].size();i++)
    {
        if(a[x][i].fr==p)continue;
        if(viz[a[x][i].fr])fup[x]=min(fup[x],fin[a[x][i].fr]);
        else
        {
            dfs(a[x][i].fr,x);
            fup[x]=min(fup[x],fup[a[x][i].fr]);
            if(fup[a[x][i].fr]>fin[x])brg.pb(a[x][i].sc);
        }
    }
}
void dfs2(int x)
{
	viz[x]=1;
	vl[x]=k;
	for(int i=0;i<a[x].size();i++)
	{
		if(viz[a[x][i].fr] || vb[a[x][i].sc])continue;
		dfs2(a[x][i].fr);
	}
}
void dfs3(int x,int p,int ed)
{
	for(int i=0;i<gr[x].size();i++)
	{
		if(gr[x][i].fr==p)continue;
		dfs3(gr[x][i].fr,x,gr[x][i].sc);
		val[x]+=val[gr[x][i].fr];
		var[x]+=var[gr[x][i].fr];
	}
	if(val[x]>0 && ed)
	{
		if(vl[edg[ed].fr]==x)rs[ed]='R';
		else rs[ed]='L';
	}
	if(var[x]>0 && ed)
	{
		if(vl[edg[ed].fr]==x)rs[ed]='L';
		else rs[ed]='R';
	}
}
void bld(int x,int p,int ed)
{
	viz[x]=1;
	vc.pb(x);
    tin[x]=++t;
	up[x][0]=p,pr[x]=p;
    e[x]=ed;
    for(int i=1;i<18;i++)up[x][i]=up[up[x][i-1]][i-1];
    for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x,gr[x][i].sc);
    tout[x]=++t;
}
int anc(int x,int y)
{
    return tin[x]<=tin[y] && tout[x]>=tout[y];
}
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(up[x][i],y))x=up[x][i];
    return up[x][0];
}
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>>x>>y;
        a[x].pb(mkp(y,i));
        a[y].pb(mkp(x,i));
        edg[i]=mkp(x,y);
    }
    //memset(fin,-1,sizeof(fin));
    //memset(fup,-1,sizeof(fup));
   	for(i=1;i<=n;i++)
   	{
   		if(viz[i])continue;
		dfs(i,i);	
	}
	for(i=0;i<brg.size();i++)vb[brg[i]]=1;
	for(i=1;i<=m;i++)rs[i]='B';
	memset(viz,0,sizeof(viz));
	for(i=1;i<=n;i++)
	{
		if(viz[i])continue;
		k++;
		dfs2(i);
		//cout<<k<<" "<<i<<endl;
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<a[i].size();j++)
		{
			if(vb[a[i][j].sc])
			{
				gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
				//cout<<vl[i]<<" "<<vl[a[i][j].fr]<<endl;
			}
		}
	}
	cin>>nr;
	for(i=1;i<=nr;i++)
	{
		cin>>x>>y;
		if(vl[x]!=vl[y])q[vl[x]].pb(vl[y]);
	}
	memset(viz,0,sizeof(viz));
	for(i=1;i<=k;i++)
	{
		if(viz[i])continue;
		vc.clear();
		bld(i,i,0);
		for(j=0;j<vc.size();j++)
		{
			x=vc[j];
			for(r=0;r<q[x].size();r++)
			{
				l=lca(q[x][r],x);
				/*val[x]++;
				val[l]--;
				var[q[x][r]]++;
				var[l]--;*/
				y=x;
				while(y!=l)
				{
					if(vl[edg[e[y]].fr]==y)rs[e[y]]='R';
					else rs[e[y]]='L';
					y=pr[y];
					if(!y || y==i)break;
				}
				y=q[x][r];
				while(y!=l)
				{
					if(vl[edg[e[y]].fr]==y)rs[e[y]]='L';
					else rs[e[y]]='R';
					y=pr[y];
					if(!y || y==i)break;
				}
			}
		}
		//dfs3(i,0,0);
	}
	for(i=1;i<=m;i++)cout<<rs[i];
	cout<<endl;
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a[x].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:47: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 dfs3(int, int, int)':
oneway.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<gr[x].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'void bld(int, int, int)':
oneway.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x,gr[x][i].sc);
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:116:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<brg.size();i++)vb[brg[i]]=1;
          ~^~~~~~~~~~~
oneway.cpp:128:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++)
           ~^~~~~~~~~~~~
oneway.cpp:149:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vc.size();j++)
           ~^~~~~~~~~~
oneway.cpp:152:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(r=0;r<q[x].size();r++)
            ~^~~~~~~~~~~~

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