제출 #128611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128611		faustaadp	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	301 ms	44408 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];
ll bes[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)
{
	bes[aa]=Z[aa];
	b[aa]=1;
	ll ii;
	for(ii=0;ii<V[aa].size();ii++)
	{
		if(b[V[aa][ii]])continue;
		dfs3(V[aa][ii]);
		bes[aa]+=bes[V[aa][ii]];
		if((W[aa][ii]*bes[V[aa][ii]])>0LL)
			s[abs(W[aa][ii])-1]='L';
		else
		if((W[aa][ii]*bes[V[aa][ii]])<0LL)
			s[abs(W[aa][ii])-1]='R';
	}
	//cout<<aa<<" "<<bes[aa]<<"\n";
}
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);
		//	break;
		}
	}
	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);
		}
	memset(b,0,sizeof(b));
	for(i=1;i<=p;i++)
	{
		Z[nm[X[i]]]++;
		Z[nm[Y[i]]]--;
		continue;
		// 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]]]--;
	}
	//return 0;
	memset(b,0,sizeof(b));
	for(i=1;i<=JK;i++)
	{
		if(!b[i])
		{
			dfs3(i);
		}
	}
	cout<<s<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'void dfs(ll, ll)':
oneway.cpp:26: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:51: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)':
oneway.cpp:63: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:79: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: 40 / 40