#include <bits/stdc++.h>
using namespace std;
int n, m, p, ttime;
vector< vector< pair<int,int> > > grp;
vector< pair<int,int> > ribs;
vector< pair<int,int> > a;
vector<int> used, tin, tup, brg;
void dfs_time ( int v, int pind )
{
used[v] = 1;
tin[v] = tup[v] = ttime++;
for ( auto& [to,ind] : grp[v] )
if ( ind != pind )
{
if ( !used[to] )
{
dfs_time( to, ind );
if ( tup[to] > tin[v] )
brg[ind] = 1;
tup[v] = min( tup[v], tup[to] );
}
else
tup[v] = min( tup[v], tin[to] );
}
}
vector< vector<int> > tree;
vector<int> color;
int ccol;
void dfs_color ( int v, int cl )
{
color[v] = cl;
for ( auto& [to,ind] : grp[v] )
if ( !brg[ind] && !color[to] )
dfs_color( to, cl );
}
vector< vector<int> > up;
vector<int> h, ctin, ctout;
void dfs_up ( int v, int p )
{
ctin[v] = ttime++;
up[v][0] = p;
for ( int i=1; i<21; i++ )
if ( up[v][i-1] != -1 )
up[v][i] = up[ up[v][i-1] ][i-1];
for ( auto& to : tree[v] )
if ( to != p )
{
h[to] = h[v] + 1;
dfs_up( to, v );
}
ctout[v] = ttime++;
}
int lca ( int u, int v )
{
if ( u == v )
return u;
if ( h[u] > h[v] )
swap( u, v );
for ( int i=20; i>=0; i-- )
if ( up[v][i] != -1 )
{
int to = up[v][i];
if ( ctin[to] <= ctin[u] && ctout[to] >= ctout[u] )
continue;
v = to;
}
return up[v][0];
}
vector<int> rib_dir;
int dfs_dir ( int v, int p )
{
for ( auto& to : tree[v] )
if ( to != p )
rib_dir[v] += dfs_dir( to, v );
return rib_dir[v];
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
grp.assign( n+1, vector< pair<int,int> >() );
for ( int i=0; i<m; i++ )
{
int u, v;
cin >> u >> v;
grp[u].push_back({ v, i });
grp[v].push_back({ u, i });
ribs.push_back({ u, v });
}
cin >> p;
a.resize( p );
for ( auto& [x,y] : a )
cin >> x >> y;
used = tin = tup = vector<int>( n+1, 0 );
brg.assign( m, 0 );
for ( int i=1; i<=n; i++ )
if ( !used[i] )
dfs_time( i, -1 );
color.assign( n+1, 0 );
for ( int i=1; i<=n; i++ )
if ( !color[i] )
dfs_color( i, ++ccol );
/*for ( int i=1; i<=n; i++ )
cout << color[i] << ' ';
cout << '\n';*/
tree.assign( ccol+1, vector<int>() );
for ( int i=1; i<=n; i++ )
for ( auto& [to,ind] : grp[i] )
if ( i < to && brg[ind] )
{
tree[ color[i] ].push_back( color[to] );
tree[ color[to] ].push_back( color[i] );
}
/*cout << "tree:\n";
for ( int i=1; i<=ccol; i++ )
{
cout << i << ": ";
for ( auto& to : tree[i] )
cout << to << ' ';
cout << '\n';
}*/
up.assign( ccol+1, vector<int>( 21, -1 ) );
h = ctin = ctout = vector<int>( ccol+1, 0 );
dfs_up( 1, -1 );
rib_dir.assign( ccol+1, 0 );
for ( auto& [x,y] : a )
{
x = color[x];
y = color[y];
if ( x == y )
continue;
int w = lca( x, y );
rib_dir[x]++;
rib_dir[w]--;
rib_dir[y]--;
rib_dir[w]++;
}
dfs_dir( 1, -1 );
for ( auto& [x,y] : ribs )
{
if ( color[x] == color[y] )
cout << 'B';
else
{
x = color[x];
y = color[y];
int w = h[x] < h[y] ? y : x;
if ( rib_dir[w] == -1 )
cout << ( w == y ? 'R' : 'L' );
else if ( rib_dir[w] == 1 )
cout << ( w == y ? 'L' : 'R' );
else
cout << 'B';
}
}
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs_time(int, int)':
oneway.cpp:17:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for ( auto& [to,ind] : grp[v] )
| ^
oneway.cpp: In function 'void dfs_color(int, int)':
oneway.cpp:42:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for ( auto& [to,ind] : grp[v] )
| ^
oneway.cpp: In function 'int main()':
oneway.cpp:128:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
128 | for ( auto& [x,y] : a )
| ^
oneway.cpp:151:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
151 | for ( auto& [to,ind] : grp[i] )
| ^
oneway.cpp:175:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
175 | for ( auto& [x,y] : a )
| ^
oneway.cpp:194:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
194 | for ( auto& [x,y] : ribs )
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
