#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
using namespace std;
const int maxn=1e5+5;
struct union_find{
int parent[maxn];
int sz[maxn];
union_find(){
for(int i=0; i<maxn; i++){
parent[i]=i;
sz[i]=1;
}
}
int find(int x){
if(parent[x]==x){
return x;
}
return parent[x]=find(parent[x]);
}
void update(int x, int y){
x=find(x);
y=find(y);
if(sz[x]>sz[y]){
swap(x, y);
}
parent[x]=y;
sz[y]+=sz[x];
}
bool query(int x, int y){
return find(x)==find(y);
}
};
union_find U;
vector < array < int, 3 > > ms[maxn];
vector < array < int, 4 > > most;
int sol[maxn];
bool bio[maxn];
int disc[maxn];
int mini[maxn];
void dfs(int x, int prosl){
bio[x]=1;
if(prosl==x){
disc[x]=0;
}
else{
disc[x]=disc[prosl]+1;
}
bool p=0;
mini[x]=disc[x];
int y;
for(int i=0; i<(int)ms[x].size(); i++){
y=ms[x][i][0];
if(!bio[y]){
dfs(y, x);
mini[x]=min(mini[x], mini[y]);
if(disc[x]<mini[y]){
most.push_back({x, y, ms[x][i][1], ms[x][i][2]});
}
else{
if(!U.query(x, y)){
U.update(x, y);
}
}
}
else{
if(!p && y==prosl){
p=1;
}
else{
mini[x]=min(mini[x], disc[y]);
}
}
}
}
vector < array < int, 3 > > novi[maxn];
int val[maxn];
int dfs1(int x, int prosl, int edge, bool p){
int sum=val[x];
for(int i=0; i<(int)novi[x].size(); i++){
if(prosl!=novi[x][i][0]){
sum+=dfs1(novi[x][i][0], x, novi[x][i][1], novi[x][i][2]^1);
}
}
if(sum>0){
if(p){
sol[edge]=1;
}
else{
sol[edge]=-1;
}
}
else if(sum<0){
if(p){
sol[edge]=-1;
}
else{
sol[edge]=1;
}
}
return sum;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int a, b;
for(int i=0; i<m; i++){
cin >> a >> b;
a--;
b--;
ms[a].push_back({b, i, 1});
ms[b].push_back({a, i, 0});
}
for(int i=0; i<n; i++){
if(!bio[i]){
dfs(i, i);
}
}
/* for(int i=0; i<(int)most.size(); i++){
cout << most[i][0] << ' ' << most[i][1] << endl;
}
for(int i=0; i<n; i++){
cout << disc[i] << ' ';
}
cout << endl;*/
for(int i=0; i<(int)most.size(); i++){
novi[U.find(most[i][0])].push_back({U.find(most[i][1]), most[i][2], most[i][3]});
novi[U.find(most[i][1])].push_back({U.find(most[i][0]), most[i][2], most[i][3]^1});
}
int q;
cin >> q;
for(int i=0; i<q; i++){
cin >> a >> b;
a--;
b--;
a=U.find(a);
b=U.find(b);
val[a]++;
val[b]--;
}
dfs1(U.find(0), -1, m, 0);
for(int i=0; i<m; i++){
if(!sol[i]){
cout << "B";
}
else if(sol[i]==1){
cout << "R";
}
else{
cout << "L";
}
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
