oj.uz

Submission #158580

# Submission time Handle Problem Language Result Execution time Memory
158580 2019-10-18T01:48:58 Z Lawliet One-Way Streets (CEOI17_oneway) C++14
100 / 100
 167 ms 23316 KB 
#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];

int min(int& a, int& b)
{
	if(a < b) return a;
	return b;
}

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

oneway.cpp: In function 'void DFSLowlink(int, int)':
oneway.cpp:32: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:60: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:65: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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
oneway.cpp:82: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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7412 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 9 ms 7544 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7412 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 9 ms 7544 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7420 KB Output is correct
11 Correct 85 ms 13432 KB Output is correct
12 Correct 104 ms 14888 KB Output is correct
13 Correct 120 ms 16772 KB Output is correct
14 Correct 127 ms 18480 KB Output is correct
15 Correct 148 ms 18936 KB Output is correct
16 Correct 127 ms 18552 KB Output is correct
17 Correct 166 ms 20216 KB Output is correct
18 Correct 163 ms 18808 KB Output is correct
19 Correct 167 ms 21356 KB Output is correct
20 Correct 116 ms 15268 KB Output is correct
21 Correct 86 ms 15224 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7412 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 9 ms 7544 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7420 KB Output is correct
11 Correct 85 ms 13432 KB Output is correct
12 Correct 104 ms 14888 KB Output is correct
13 Correct 120 ms 16772 KB Output is correct
14 Correct 127 ms 18480 KB Output is correct
15 Correct 148 ms 18936 KB Output is correct
16 Correct 127 ms 18552 KB Output is correct
17 Correct 166 ms 20216 KB Output is correct
18 Correct 163 ms 18808 KB Output is correct
19 Correct 167 ms 21356 KB Output is correct
20 Correct 116 ms 15268 KB Output is correct
21 Correct 86 ms 15224 KB Output is correct
22 Correct 144 ms 20328 KB Output is correct
23 Correct 142 ms 18680 KB Output is correct
24 Correct 158 ms 18808 KB Output is correct
25 Correct 154 ms 23316 KB Output is correct
26 Correct 137 ms 19832 KB Output is correct
27 Correct 145 ms 18916 KB Output is correct
28 Correct 66 ms 10488 KB Output is correct
29 Correct 136 ms 14684 KB Output is correct
30 Correct 135 ms 15160 KB Output is correct
31 Correct 162 ms 15100 KB Output is correct
32 Correct 156 ms 18040 KB Output is correct