#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <string.h>
#include <bitset>
#include <numeric>
#include <utility>
#include <random>
#include <cassert>
#include<stack>
using namespace std;
//Arrays
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb(a,x) lower_bound(a.begin(), a.end(), x)
#define ub(a,x) upper_bound(a.begin(), a.end(), x)
#define mems(x) memset(x, 0, sizeof(x))
#define sz(a) ((int)a.size())
#define all(x) x.begin(), x.end()
#define fr first
#define sc second
//Input / Output
#define psn(x) cout<<x<<'\n'
#define pss(x) cout<<x<<' '
#define ps(x)cout<<x
#define debug(x) cout<<'['<<#x<<" = "<<x<<"]\n"
//Data Structures
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
//Order Statistic Tree
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;*/
int dfn[200001], low[200001];
vector<int>g[200001];
int pos=1;
int scc=0;
int comp[200001];
vector<int>nov[200001];
int dp[200001];
int dist[200001];
stack<int>inst;
void tarjan(int v, int p = -1){
bool pp=0;
inst.push(v);
low[v]=dfn[v]=++pos;
for(auto i:g[v]){
if(i!=p||pp){
if(!dfn[i]){
tarjan(i,v);
low[v]=min(low[v],low[i]);
}
else low[v]=min(low[v],dfn[i]);
}
else pp=1;
}
if(low[v]==dfn[v]){
while(inst.top()!=v){
comp[inst.top()]=scc;
inst.pop();
}
comp[v]=scc++; inst.pop();
}
}
void dfs(int v, int p = -1){
for(int& x : nov[v]){
if (x != p){
dist[x] = dist[v] + 1;
dfs(x, v);
dp[v] += dp[x];
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
memset(dfn ,0 ,sizeof(dfn));
memset(dp, 0, sizeof(dp));
memset(dist, 0, sizeof(dist));
int n, m;
cin >> n >> m;
vector<pii>edges;
for(int i = 0; i < m ; i++){
int a,b;
cin >> a >> b;
g[a].eb(b);
g[b].eb(a);
edges.eb(mp(a,b));
}
int p;
cin >> p;
//vector<pair<int,int>>edges;
for (int i = 1; i<= n; i++){
if(!dfn[i])tarjan(i);
}
for (int i = 1; i<=n; i++){
for (int x : g[i]){
if (comp[x] != comp[i]){
nov[x].eb(i);
nov[i].eb(x);
}
}
}
for (int i = 0; i < p; i++){
int a,b;cin >> a >> b;
dp[comp[a]]++;
dp[comp[b]]--;
}
for (int i = 0; i < scc; i++){
if(!dist[i])dfs(i);
}
for (auto i : edges){
if (comp[i.fr] == comp[i.sc]){
ps("B");continue;
}
i.fr = comp[i.fr];
i.sc = comp[i.sc];
if (dist[i.fr] > dist[i.sc]){
if (dp[i.fr] >= 1){
//i.sc is below i.fr
//i.fr needs to go upwards
cout<<'L';
}
if (dp[i.fr] == 0){
cout<<'B';
}
if (dp[i.fr] < 0)cout<<'R';
}else{
if (dp[i.fr] >= 1){
//i.fr is below i.sc
//i.sc needs to go upwards
cout<<'R';
}
if (dp[i.fr] == 0){
cout<<'B';
}
if (dp[i.fr]< 0)cout<<'L';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
