oj.uz

Submission #446618

# Submission time Handle Problem Language Result Execution time Memory
446618 2021-07-22T19:41:15 Z renzo1805 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 189 ms 33252 KB 
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 100005;
const int LOG = 19;
typedef pair<int, int> edge;

int N, M, Q;
edge E[MAXN];
char res[MAXN];
vector<int> G[MAXN];
vector<int> T[MAXN];

int P[MAXN][LOG];
int L[MAXN];
int up[MAXN];
int X[MAXN], Y[MAXN]; 

int f[MAXN]; // for merging edges
int dfsnum[MAXN];
int low[MAXN];
int num;


inline int find_set( const int &u ){
	return u == f[u]? u:( f[u] = find_set( f[u] ) ); 
}

inline int nxt( const int &e, const int &u ){
	return E[e].first == u? E[e].second:E[e].first;
}

int lca( int u, int v ){
	if ( L[u] > L[v] ) swap( u, v );
	if ( u == v ) return u;
	for ( int i=LOG - 1; i >= 0; --i )
		if ( L[v] - (1 << i) >= L[u] ){
			v = P[v][i];
		}
	if ( u == v ) return u;
	for ( int i=LOG - 1; i >= 0; --i ){
		if ( P[u][i] != -1 && P[u][i] != P[v][i] )
			u = P[u][i], v = P[v][i];
	}
	return P[u][0];
}

void dfs( const int &u, const int &p ){
	int v, e;
	dfsnum[ u ] = low[ u ] = num++;
	for ( int i=0; i < (int)G[u].size(); ++i ){
		e = G[u][i];
		v = nxt( e, u );
		if ( e == p ) continue;
		if ( dfsnum[v] == -1 ){
			dfs( v, e );
			low[u] = min( low[u], low[v] );
		}
		else {	// back edge
			low[u] = min( low[u], dfsnum[v] );
		}
		if ( low[v] <= dfsnum[u] ){	// Not a bridge
			int ru = find_set( u );
			int rv = find_set( v );
			if ( ru != rv ){ 
				if ( dfsnum[ru] < dfsnum[rv] )
					f[ rv ] = ru;
				else 
					f[ ru ] = rv;
			}
			res[ e ] = 'B';	
		}
	}
}

void level( const int &u ){
	int e;
	int v;	
	for ( int i=0; i < (int)T[u].size(); ++i ){
		e = T[u][i];
		v = nxt( e, u );
		L[v] = L[u] + 1;
		level( v );
	}
}

void merge( int u, int v, const int &d ){
	//printf("merge %d %d %d\n", u + 1, v + 1, d);
	int e;
	int rx, ry;
	while ( L[u] > L[v] ){
		e = up[ u ];
		//printf("edge %d: %d - %d\n", e + 1, E[e].first + 1, E[e].second + 1 );
		rx = find_set( E[e].first );
		ry = find_set( E[e].second );
		if ( rx == u ){
			res[ e ] = ( d > 0 )? 'R':'L';
			f[ rx ] = ry;
			u = ry;	
			//printf("vertices %d - %d - %c\n", rx + 1, ry + 1, res[e] );
		}
		else {
			res[ e ] = ( d > 0 )? 'L':'R'; 
			f[ ry ] = rx;
			u = rx;
			//printf("vertices %d - %d - %c\n", rx + 1, ry + 1, res[e] );
		}
	}
}

int main(){
	int u, v, w;

	scanf("%d %d", &N, &M);

	fill( res, res + M, '-' );

	for ( int i=0; i < M; ++i ){
		scanf("%d %d", &u, &v);
		u--, v--;
		E[i].first = u, E[i].second = v;
		if ( u == v ){
			res[i] = 'B';
			continue;
		}
		G[u].push_back( i ), G[v].push_back( i );
	}
	
	for ( int i=0; i < N; ++i ) f[i] = i;

	fill( dfsnum, dfsnum + N, -1 );
	num = 0;
	for ( int i=0; i < N; ++i )
		if ( dfsnum[i] == -1 )
			dfs( i, -1 );
	// Initialize for LCA computation
	for ( int i=0; i < N; ++i )
		for ( int j=0; j < LOG; ++j )
			P[i][j] = -1;
	fill( up, up + N, -1 );
	// Create a tree from the bridges
	for ( int i=0; i < M; ++i ){
		u = E[i].first, v = E[i].second;
		//printf("Previous edge (%d, %d)\n", u + 1, v + 1);
		u = find_set( u ), v = find_set( v );	
		if ( u != v ){
			E[i].first = u, E[i].second = v;
			//printf("New edge (%d, %d)\n", u + 1, v + 1);			
			if ( dfsnum[u] < dfsnum[v] ){ 
				T[u].push_back( i );
				P[v][0] = u;
				up[ v ] = i;	// edge to go up in the tree
				//printf("Tree arc %d -> %d\n", u + 1, v + 1);
			}
			else { 
				//printf("Tree arc %d -> %d\n", v + 1, u + 1);				
				T[v].push_back( i ); 
				up[ u ] = i;	// edge to go up in the tree
				P[u][0] = v;
			}
		}
	}
	scanf("%d", &Q);
	for ( int i=0; i < Q; ++i ){
		scanf("%d %d", X + i, Y + i);
		X[i]--, Y[i]--;
		X[i] = find_set( X[i] );
		Y[i] = find_set( Y[i] );
	}
	// Find the level of each vertex
	for ( int i=0; i < N; ++i ){
		if ( find_set( i ) == i && P[i][0] == -1 ){
			L[i] = 0;
			level( i );
		}
	}
	// Binary lifting
	for ( int j=1; j < LOG; ++j )
		for ( int i=0; i < N; ++i ){
			if ( P[i][j - 1] != -1 )
				P[i][j] = P[ P[i][j - 1] ][j -  1]; 
		}

	for ( int i=0; i < Q; ++i ){
		//puts("");
		u = X[i], v = Y[i];
		w = lca( u, v );
		// Look for the sets containing these vertices
		u = find_set( u );
		v = find_set( v );
		w = find_set( w );
		if ( u != w ) merge( u, w, 1 );
		if ( v != w ) merge( v, w, -1 );
	}	
	for ( int i=0; i < M; ++i ){
		if ( res[i] == '-' ) res[i] = 'B';
		putchar( res[i] );
	}	
	puts("");

	return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:163:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%d %d", X + i, Y + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 3 ms 5188 KB Output is correct
7 Correct 3 ms 5196 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5124 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 3 ms 5188 KB Output is correct
7 Correct 3 ms 5196 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5124 KB Output is correct
11 Correct 52 ms 12612 KB Output is correct
12 Correct 62 ms 15332 KB Output is correct
13 Correct 67 ms 18532 KB Output is correct
14 Correct 80 ms 22036 KB Output is correct
15 Correct 89 ms 23108 KB Output is correct
16 Correct 94 ms 21288 KB Output is correct
17 Correct 94 ms 25156 KB Output is correct
18 Correct 105 ms 21372 KB Output is correct
19 Correct 94 ms 27528 KB Output is correct
20 Correct 59 ms 16036 KB Output is correct
21 Correct 54 ms 15684 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 3 ms 5188 KB Output is correct
7 Correct 3 ms 5196 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5124 KB Output is correct
11 Correct 52 ms 12612 KB Output is correct
12 Correct 62 ms 15332 KB Output is correct
13 Correct 67 ms 18532 KB Output is correct
14 Correct 80 ms 22036 KB Output is correct
15 Correct 89 ms 23108 KB Output is correct
16 Correct 94 ms 21288 KB Output is correct
17 Correct 94 ms 25156 KB Output is correct
18 Correct 105 ms 21372 KB Output is correct
19 Correct 94 ms 27528 KB Output is correct
20 Correct 59 ms 16036 KB Output is correct
21 Correct 54 ms 15684 KB Output is correct
22 Correct 184 ms 27132 KB Output is correct
23 Correct 171 ms 23636 KB Output is correct
24 Correct 154 ms 23216 KB Output is correct
25 Correct 189 ms 33252 KB Output is correct
26 Correct 171 ms 26244 KB Output is correct
27 Correct 181 ms 23796 KB Output is correct
28 Correct 56 ms 8988 KB Output is correct
29 Correct 87 ms 17176 KB Output is correct
30 Correct 91 ms 17604 KB Output is correct
31 Correct 92 ms 18164 KB Output is correct
32 Correct 123 ms 24056 KB Output is correct