oj.uz

Submission #128611

# Submission time Handle Problem Language Result Execution time Memory
128611 2019-07-11T07:28:11 Z faustaadp One-Way Streets (CEOI17_oneway) C++17
100 / 100
 301 ms 44408 KB 
#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";
}

Compilation message

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13048 KB Output is correct
2 Correct 14 ms 13072 KB Output is correct
3 Correct 14 ms 13176 KB Output is correct
4 Correct 14 ms 13304 KB Output is correct
5 Correct 14 ms 13304 KB Output is correct
6 Correct 13 ms 13176 KB Output is correct
7 Correct 14 ms 13304 KB Output is correct
8 Correct 14 ms 13304 KB Output is correct
9 Correct 13 ms 13176 KB Output is correct
10 Correct 13 ms 13152 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13048 KB Output is correct
2 Correct 14 ms 13072 KB Output is correct
3 Correct 14 ms 13176 KB Output is correct
4 Correct 14 ms 13304 KB Output is correct
5 Correct 14 ms 13304 KB Output is correct
6 Correct 13 ms 13176 KB Output is correct
7 Correct 14 ms 13304 KB Output is correct
8 Correct 14 ms 13304 KB Output is correct
9 Correct 13 ms 13176 KB Output is correct
10 Correct 13 ms 13152 KB Output is correct
11 Correct 88 ms 21788 KB Output is correct
12 Correct 98 ms 23584 KB Output is correct
13 Correct 135 ms 25432 KB Output is correct
14 Correct 165 ms 29004 KB Output is correct
15 Correct 183 ms 30540 KB Output is correct
16 Correct 226 ms 36856 KB Output is correct
17 Correct 195 ms 37992 KB Output is correct
18 Correct 238 ms 37372 KB Output is correct
19 Correct 197 ms 38880 KB Output is correct
20 Correct 94 ms 23028 KB Output is correct
21 Correct 95 ms 23672 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13048 KB Output is correct
2 Correct 14 ms 13072 KB Output is correct
3 Correct 14 ms 13176 KB Output is correct
4 Correct 14 ms 13304 KB Output is correct
5 Correct 14 ms 13304 KB Output is correct
6 Correct 13 ms 13176 KB Output is correct
7 Correct 14 ms 13304 KB Output is correct
8 Correct 14 ms 13304 KB Output is correct
9 Correct 13 ms 13176 KB Output is correct
10 Correct 13 ms 13152 KB Output is correct
11 Correct 88 ms 21788 KB Output is correct
12 Correct 98 ms 23584 KB Output is correct
13 Correct 135 ms 25432 KB Output is correct
14 Correct 165 ms 29004 KB Output is correct
15 Correct 183 ms 30540 KB Output is correct
16 Correct 226 ms 36856 KB Output is correct
17 Correct 195 ms 37992 KB Output is correct
18 Correct 238 ms 37372 KB Output is correct
19 Correct 197 ms 38880 KB Output is correct
20 Correct 94 ms 23028 KB Output is correct
21 Correct 95 ms 23672 KB Output is correct
22 Correct 246 ms 39800 KB Output is correct
23 Correct 243 ms 41080 KB Output is correct
24 Correct 272 ms 41464 KB Output is correct
25 Correct 247 ms 44408 KB Output is correct
26 Correct 225 ms 41884 KB Output is correct
27 Correct 301 ms 41092 KB Output is correct
28 Correct 58 ms 21496 KB Output is correct
29 Correct 119 ms 26460 KB Output is correct
30 Correct 124 ms 26972 KB Output is correct
31 Correct 136 ms 26932 KB Output is correct
32 Correct 156 ms 32504 KB Output is correct