#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second
const int maxn = 100000;
int n, m, k;
pi e[maxn];
int t[maxn], l[maxn], p[maxn], dp[maxn];
bool used[maxn], used2[maxn];
vector<pi> graph[maxn], graph2[maxn];
vector<int> b[maxn];
int s;
string ret;
void dfs2(int c){
p[c] = s;
b[s].push_back(c);
for(pi i : graph[c]){
if(p[i.f] != -1){
if(p[i.f] != -2 && p[i.f] != s){
graph2[s].push_back({p[i.f], i.s});
graph2[p[i.f]].push_back({s, i.s});
}
continue;
}
dfs2(i.f);
}
}
int x;
void dfs(int c){
used[c] = 1;
t[c] = l[c] = x++;
for(pi i : graph[c]){
if(used2[i.s]) continue;
used2[i.s] = 1;
if(used[i.f]){
l[c] = min(l[c], t[i.f]);
}else{
dfs(i.f);
l[c] = min(l[c], l[i.f]);
if(l[i.f] > t[c]){
p[c] = -2;
dfs2(i.f);
s++;
p[c] = -1;
}
}
used2[i.s] = 0;
}
if(!c){
dfs2(c);
s++;
}
}
int dfs3(int c, int pc = -1){
for(pi i : graph2[c]){
if(i.f == pc) continue;
dp[c] += dfs3(i.f, c);
if(dp[i.f] < 0){
ret[i.s] = p[e[i.s].f] == c ? 'L' : 'R';
}
if(dp[i.f] > 0){
ret[i.s] = p[e[i.s].f] == c ? 'R' : 'L';
}
}
return dp[c];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> e[i].f >> e[i].s;
e[i].f--, e[i].s--;
graph[e[i].f].push_back({e[i].s, i});
graph[e[i].s].push_back({e[i].f, i});
}
memset(p, -1, sizeof(p));
dfs(0);
cin >> k;
for(int i = 0; i < k; i++){
int a, b;
cin >> a >> b;
a--, b--;
dp[p[a]]--;
dp[p[b]]++;
}
ret = string(m, 'B');
dfs3(0);
cout << ret << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
