Submission #128575

#	Time	Username	Problem	Language	Result	Execution time	Memory
128575		faustaadp	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3037 ms	42616 KiB

oneway

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,p,i,x[101010],y[101010],X[101010],Y[101010],j,te,JK;
vector<ll> v[101010],w[101010],V[101010],isi[101010],W[101010];
ll b[101010];
ll nm[101010];
ll Z[101010];
ll br[101010];
ll wk[101010];
ll mi[101010];
string s;
pair<ll,ll> P[101010];
void dfs(ll aa,ll bb)
{
	te++;
	wk[aa]=te;
	mi[aa]=te;
	b[aa]=1;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(abs(w[aa][ii])==bb)continue;
		if(b[v[aa][ii]]==0)
		{
			dfs(v[aa][ii],abs(w[aa][ii]));
			mi[aa]=min(mi[aa],mi[v[aa][ii]]);
			if(wk[aa]<mi[v[aa][ii]])
			{
				br[abs(w[aa][ii])]=1;
				//cout<<aa<<" "<<v[aa][ii]<<"\n";
			}
		}
		else
		{
			mi[aa]=min(mi[aa],wk[v[aa][ii]]);
		}
	}
}
void dfs2(ll aa)
{
	b[aa]=1;
	nm[aa]=JK;
	isi[JK].pb(aa);
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(br[abs(w[aa][ii])])continue;
		if(b[v[aa][ii]])continue;
		dfs2(v[aa][ii]);
	}
}
void dfs3(ll aa,ll bb)
{
	b[aa]=1;
	ll ii;
	for(ii=0;ii<V[aa].size();ii++)
	{
		if(b[V[aa][ii]])continue;
		if(bb)
		{
			if((w[aa][ii]*bb)>0LL)
				s[abs(w[aa][ii])]='R';
			else
				s[abs(w[aa][ii])]='L';
		}
		dfs3(V[aa][ii],bb+Z[V[aa][ii]]);
	}
}
void dfs4(ll aa,ll bb)
{
	ll ii;
	for(ii=0;ii<V[aa].size();ii++)
		if(V[aa][ii]!=bb)
		{
			P[V[aa][ii]]=mp(aa,W[aa][ii]);
			dfs4(V[aa][ii],aa);
		}
}
int main()
{
	//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>x[i]>>y[i];
		v[x[i]].pb(y[i]);
		w[x[i]].pb(i);
		v[y[i]].pb(x[i]);
		w[y[i]].pb(-i);
		s+="B";
	}
	cin>>p;
	for(i=1;i<=p;i++)cin>>X[i]>>Y[i];
	for(i=1;i<=n;i++)
	{
		if(!b[i])
			dfs(i,i);
	}
	memset(b,0,sizeof(b));
	for(i=1;i<=n;i++)
		if(!b[i])
		{
			JK++;
			dfs2(i);
		}
	//return 0;
	for(i=1;i<=m;i++)
		if(br[i])
		{
		//	cout<<nm[x[i]]<<" "<<nm[y[i]]<<"_\n";
			V[nm[x[i]]].pb(nm[y[i]]);
			W[nm[x[i]]].pb(i);
			V[nm[y[i]]].pb(nm[x[i]]);
			W[nm[y[i]]].pb(-i);
		}
	for(i=1;i<=p;i++)
	{
		dfs4(nm[X[i]],nm[X[i]]);
		P[nm[X[i]]]=mp(-1,-1);
		ll tem=nm[Y[i]];
		while(tem!=nm[X[i]])
		{
			//cout<<abs(P[tem].se)<<"_\n";
			if(P[tem].se<0)
				s[abs(P[tem].se)-1]='L';
			else
				s[abs(P[tem].se)-1]='R';
			tem=P[tem].fi;
			//cout<<tem<<"\n";
			//break;	
		}
		//cout<<nm[X[i]]<<" "<<nm[Y[i]]<<"\n";
		//Z[nm[X[i]]]++;
		//Z[nm[Y[i]]]--;
	}
	cout<<s<<"\n";
	//return 0;
	memset(b,0,sizeof(b));
	for(i=1;i<=JK;i++)
	{
		if(!b[i])
		{
			dfs3(i,Z[i]);
		}
	}
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(ll, ll)':
oneway.cpp:25:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(ll)':
oneway.cpp:50:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(ll, ll)':
oneway.cpp:61:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<V[aa].size();ii++)
           ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs4(ll, ll)':
oneway.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<V[aa].size();ii++)
           ~~^~~~~~~~~~~~~

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