#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v;
bool operator == ( const edge &x ) const {
return (u == x.u && v == x.v) || (u == x.v && u == x.u);
}
bool operator != ( const edge &x ) const {
return !(edge{ u, v } == x);
}
};
const int none = 0;
const int up = 1;
const int down = 2;
const int MAX_N = 1e5;
const int MAX_M = 1e5;
bool vis[MAX_N + 1], isInBiconex[MAX_N + 1];
int depth[MAX_N + 1], climbDepth[MAX_N + 1], countEdges[MAX_N + 1], vertexArt[MAX_N + 1], vertexBic[MAX_N + 1], biconex[MAX_N + 1], depthArb[MAX_N + 1], parent[MAX_N + 1], art[MAX_N + 1], dir[MAX_N + 1];
vector<int> adj[MAX_N + 1], arbAdj[MAX_N + 1];
edge edges[MAX_M];
vector<int> articulation;
vector<vector<int>> biconexe;
unordered_map<int, bool> direction[MAX_N + 1];
vector<edge> edgeStack;
void findBiconexe( int u, int p ) {
vis[u] = true;
depth[u] = depth[p] + 1;
climbDepth[u] = depth[u];
int c = 0;
for ( int v: adj[u] ) {
if ( v == p )
continue;
if ( vis[v] ) {
if ( depth[v] < depth[u] ) {
edgeStack.push_back( { u, v } );
climbDepth[u] = min( climbDepth[u], depth[v] );
}
} else {
edgeStack.push_back( { u, v } );
c++;
findBiconexe( v, u );
climbDepth[u] = min( climbDepth[u], climbDepth[v] );
if ( climbDepth[v] >= depth[u] ) {
biconexe.push_back( {} );
if ( p != 0 )
articulation.push_back( u );
edge e;
do {
e = edgeStack.back();
edgeStack.pop_back();
countEdges[biconexe.size() - 1]++;
if ( !isInBiconex[e.u] ) {
biconexe.back().push_back( e.u );
isInBiconex[e.u] = true;
}
if ( !isInBiconex[e.v] ) {
biconexe.back().push_back( e.v );
isInBiconex[e.v] = true;
}
} while ( e != edge{ u, v } );
for ( int w: biconexe.back() )
isInBiconex[w] = false;
}
}
}
if ( p == 0 && c > 1 )
articulation.push_back( u );
}
void dfs( int u, int p ) {
parent[u] = p;
depthArb[u] = depthArb[p] + 1;
for ( int v: arbAdj[u] ) {
if ( v == p )
continue;
dfs( v, u );
}
}
int main() {
int n, m;
cin >> n >> m;
for ( int i = 0; i < m; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
edges[i] = { u, v };
}
findBiconexe( 1, 0 );
/*for ( vector<int> b: biconexe ) {
for ( int v: b )
cout << v << " ";
cout << "\n";
}
for ( int v: articulation )
cout << v << " ";
cout << "\n";*/
int vert = 0;
for ( int v: articulation ) {
vertexArt[v] = ++vert;
art[vert] = vertexArt[v];
}
for ( int i = 0; i < biconexe.size(); i++ ) {
vertexBic[i] = ++vert;
for ( int v: biconexe[i] ) {
if ( vertexArt[v] ) {
arbAdj[vertexArt[v]].push_back( vertexBic[i] );
arbAdj[vertexBic[i]].push_back( vertexArt[v] );
//printf( "edgearb %d %d %d %d\n", v, i, vertexArt[v], vertexBic[i] );
} else
biconex[v] = i;
}
}
dfs( 1, 0 );
int k;
cin >> k;
for ( int v = 1; v <= vert; v++ )
dir[v] = none;
for ( int i = 0; i < k; i++ ) {
int u, v;
cin >> u >> v;
u = (vertexArt[u] ? vertexArt[u] : vertexBic[biconex[u]]);
v = (vertexArt[v] ? vertexArt[v] : vertexBic[biconex[v]]);
//printf( "%d %d\n", u, v );
while ( depthArb[u] > depthArb[v] ) {
if ( u > articulation.size() )
dir[u] = up;
//printf( "%d\n", u );
u = parent[u];
}
while ( depthArb[v] > depthArb[u] ) {
if ( v > articulation.size() )
dir[v] = down;
// printf( "%d\n", v );
v = parent[v];
}
while ( u != v ) {
//printf( "%d\n%d\n", u, v );
if ( u > articulation.size() )
dir[u] = up;
u = parent[u];
if ( v > articulation.size() )
dir[v] = down;
v = parent[v];
}
}
for ( int i = 0; i < biconexe.size(); i++ ) {
int v = vertexBic[i];
if ( countEdges[i] != 1 )
continue;
int a = biconexe[i][0], b = biconexe[i][1];
//printf( "ba %d %d %d\n", v, a, b );
if ( a == art[parent[v]] )
swap( a, b );
if ( dir[v] == up )
direction[a][b] = 1;
else
direction[b][a] = 1;
}
string ans = "";
for ( int i = 0; i < m; i++ ) {
int u = edges[i].u, v = edges[i].v;
if ( direction[u][v] )
ans += 'L';
else if ( direction[v][u] )
ans += 'R';
else
ans += 'B';
}
cout << ans;
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for ( int i = 0; i < biconexe.size(); i++ ) {
| ~~^~~~~~~~~~~~~~~~~
oneway.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | if ( u > articulation.size() )
| ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:153:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | if ( v > articulation.size() )
| ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | if ( u > articulation.size() )
| ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:163:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | if ( v > articulation.size() )
| ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:169:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for ( int i = 0; i < biconexe.size(); i++ ) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
