Submission #158578

#	Time	Username	Problem	Language	Result	Execution time	Memory
158578		Lawliet	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	186 ms	25496 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;

int n, m, q;
int curTime;

int ans[MAXN];
int low[MAXN];
int pre[MAXN];
int sub[MAXN];

bool marc[MAXN];

vector< int > adj[MAXN];
vector< int > indEdge[MAXN];
vector< int > direction[MAXN];

void DFSLowlink(int cur, int p)
{
	marc[ cur ] = true;
	low[ cur ] = pre[ cur ] = ++curTime;

	for(int i = 0 ; i < adj[ cur ].size() ; i++)
	{
		int viz = adj[ cur ][ i ];
		int ind = indEdge[ cur ][ i ];
		int d = direction[ cur ][ i ];

		if( marc[ viz ] )
		{
			if( ind != p ) low[ cur ] = min(low[ cur ] , pre[ viz ]);

			continue;
		}

		DFSLowlink( viz , ind );

		if( low[ viz ] > pre[ cur ] )
		{
			if( sub[ viz ] > 0 ) ans[ ind ] = d;
			if( sub[ viz ] < 0 ) ans[ ind ] = 3 - d;
		}

		sub[ cur ] += sub[ viz ];
		low[ cur ] = min(low[ cur ] , low[ viz ]);
	}
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int i = 1 ; i <= m ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		adj[ U ].push_back( V );
		adj[ V ].push_back( U );

		indEdge[ U ].push_back( i );
		indEdge[ V ].push_back( i );

		direction[ U ].push_back( 1 );
		direction[ V ].push_back( 2 );
	}

	scanf("%d",&q);

	for(int i = 1 ; i <= q ; i++)
	{
		int X, Y;
		scanf("%d %d",&X,&Y);

		sub[ X ]++;
		sub[ Y ]--;
	}

	for(int i = 1 ; i <= n ; i++)
		if( !marc[i] ) DFSLowlink( i , 0 );

	for(int i = 1 ; i <= m ; i++)
	{
		if(ans[ i ] == 0) printf("B");
		if(ans[ i ] == 1) printf("L");
		if(ans[ i ] == 2) printf("R");
	}
}

Compilation message (stderr)

oneway.cpp: In function 'void DFSLowlink(int, int)':
oneway.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[ cur ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
oneway.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&X,&Y);
   ~~~~~^~~~~~~~~~~~~~~

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