#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
vector<pii> edge, g[N], g2[N], query, coord;
int n, m, q, pre[N], low[N], lca[18][N], dep[N], co[N], e[N], dir[N], c;
bool bridge[M];
char label[N];
void find_bridge( int u, int p ) {
static int idx = 0;
pre[u] = low[u] = ++idx;
for( pii v : g[u] ) if( !pre[v.x] ) {
find_bridge( v.x, u );
low[u] = min( low[u], low[v.x] );
if( low[v.x] > pre[u] ) bridge[v.y] = true;
} else if( v.x != p ) low[u] = min( low[u], pre[v.x] );
}
void component( int u, int p ) {
co[u] = c;
for( pii v : g[u] ) if( v.x != p ) {
if( !co[v.x] && !bridge[v.y] ) component( v.x, u );
}
}
void init_lca( int u, int p, int ee ) {
//printf("%d\n",u);
lca[0][u] = p, dep[u] = dep[p] + 1, e[u] = ee;
for( int i = 1 ; i <= 17 ; i++ ) lca[i][u] = lca[i-1][lca[i-1][u]];
for( pii v : g2[u] ) if( v.x != p ) init_lca( v.x, u, v.y );
}
int find_lca( int a, int b ) {
if( dep[a] < dep[b] ) swap( a, b );
for( int i = 17 ; i >= 0 ; i-- ) if( dep[lca[i][a]] >= dep[b] ) a = lca[i][a];
if( a == b ) return a;
for( int i = 17 ; i >= 0 ; i-- ) if( lca[i][a] != lca[i][b] ) a = lca[i][a], b = lca[i][b];
return lca[0][a];
}
void direct( int x, int z, int di ) {
if( x == z ) return ;
if( dir[x] == 0 ) {
dir[x] = di;
int y = lca[0][x], i = e[x];
//printf("y : %d i : %d\n",y,i);
int a = co[edge[i].x], b = co[edge[i].y];
if( di == -1 ) {
if( a == x && b == y ) label[i] = 'R';
else label[i] = 'L';
} else {
if( a == y && b == x ) label[i] = 'R';
else label[i] = 'L';
}
direct( y, z, di );
}
}
int main()
{
scanf("%d %d",&n,&m);
edge.emplace_back( pii( 0, 0 ) );
for( int i = 1, a, b ; i <= m ; i++ ) {
scanf("%d %d",&a,&b);
g[a].emplace_back( pii( b, i ) ), g[b].emplace_back( pii( a, i ) );
edge.emplace_back( pii( a, b ) );
}
for( int i = 1 ; i <= n ; i++ ) if( !pre[i] ) find_bridge( i, 0 );
for( int i = 1 ; i <= n ; i++ ) if( !co[i] ) ++c, component( i, 0 );
//for( int i = 1 ; i <= n ; i++ ) printf("%d ",co[i]);
//printf("\n");
for( int i = 1 ; i <= m ; i++ ) if( bridge[i] ) {
int f = co[edge[i].x], t = co[edge[i].y];
g2[f].emplace_back( pii( t, i ) ), g2[t].emplace_back( pii( f, i ) );
}
for( int i = 1 ; i <= n ; i++ ) if( !dep[i] ) init_lca( i, 0, 0 );
for( int i = 1 ; i <= m ; i++ ) label[i] = 'B';
scanf("%d",&q);
query.emplace_back( pii( 0, 0 ) );
for( int i = 1, a, b ; i <= q ; i++ ) {
scanf("%d %d",&a,&b);
a = co[a], b = co[b];
int c = find_lca( a, b );
//printf("%d %d %d\n",a,b,c);
query.emplace_back( pii( a, b ) );
coord.emplace_back( pii( dep[c], i ) );
}
sort( coord.begin(), coord.end() );
for( pii i : coord ) {
int y = i.y;
int a = query[y].x, b = query[y].y;
int c = find_lca( a, b );
//printf("%d %d %d %d\n",a,b,c,dep[c]);
direct( a, c, -1 ), direct( b, c, 1 );
}
for( int i = 1 ; i <= m ; i++ ) printf("%c",label[i]);
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:68: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:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
~~~~~^~~~~~~~~~~~~~~
oneway.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
oneway.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 9 |
Runtime error |
362 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 9 |
Runtime error |
362 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 9 |
Runtime error |
362 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
