// Link: https://cses.fi/problemset/task/1691
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lc (node<<1)+1
#define rc (node<<1)+2
#define endl '\n'
#define INF 1e9
const int max_n = 1e5+2;
int n, m, k;
pair<int, int> edges[max_n];
vector<int> adj[max_n];
int enter[max_n], low[max_n];
int t = 0;
int scc[max_n]; // stores the id of the strongly connected component
int id = 0;
stack<int> s;
vector<int> tree[max_n];
int dp[max_n];
void dfs(int node, int parent = -1){
enter[node] = low[node] = t ++;
s.push(node);
bool pp = 0;
for(int next : adj[node]){
if(next != parent || pp){
if(enter[next] == -1){
dfs(next, node);
low[node] = min(low[node], low[next]);
if(low[next] == enter[next]){ // no edge going up
while(true){
int a = s.top();
scc[a] = id;
s.pop();
if(a == next) break;
}
id ++;
}
}
else{
low[node] = min(low[node], enter[next]);
}
}
else{
pp = 1;
}
}
}
int depth[max_n];
void dfs2(int node, int parent = -1, int dep = 0){
depth[node] = dep;
for(int next: tree[node]){
if(next == parent) continue;
dfs2(next, node, dep + 1);
dp[node] += dp[next];
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i ++){
int a, b; cin >> a >> b; a --; b --;
adj[a].push_back(b); adj[b].push_back(a);
edges[i] = {a, b};
}
// find 2-edge-connected-components and create a tree out of it
// always direct the edges from top->bottom
fill(enter, enter + n, -1);
dfs(0);
while(!s.empty()){
int a = s.top();
s.pop();
scc[a] = id;
}
id ++;
for(int i = 0; i < m; i ++){
int a = scc[edges[i].first], b = scc[edges[i].second];
if(a == b) continue;
tree[a].push_back(b);
tree[b].push_back(a);
}
// now we loop through the required passages and assign values
cin >> k;
for(int i = 0; i < k; i ++){
int a, b; cin >> a >> b; a --; b --;
a = scc[a]; b = scc[b];
dp[a]++; dp[b]--; // positive means going up, negative means going down
}
dfs2(0);
for(int i = 0; i < m; i ++){
int a = scc[edges[i].first], b = scc[edges[i].second];
if(a == b) cout << 'B';
else if(depth[b] > depth[a]){ // this means a is above b
if(dp[b] < 0){
cout << 'R';
}
else if(dp[b] == 0){
cout << 'B';
}
else if(dp[b] > 0){
cout << 'L';
}
}
else{
if(dp[a] < 0){
cout << 'L';
}
else if(dp[a] == 0){
cout << 'B';
}
else if(dp[a] > 0){
cout << 'R';
}
}
}
cout << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
