#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
int n, m;
int lvl[NMAX];
int dp[NMAX];
int viz[NMAX];
int cnt;
int dest[NMAX];
int sursa[NMAX];
int surse[NMAX];
int deste[NMAX];
int comp[NMAX];
int parent[NMAX];
vector <int> v[NMAX];
int stamp;
pii timp[NMAX];
bool par(int a, int b){
return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}
void DFS(int node, int p){
lvl[node] = lvl[p] + 1;
parent[node] = p;
for(auto x : v[node]){
if(!lvl[x]){
DFS(x, node);
dp[node] += dp[x];
}else if(lvl[x] > lvl[node]){
dp[node]--;
}else{
dp[node]++;
}
}
if(lvl[node] != 1)
dp[node]--;
}
void assignComp(int node, int p){
if(!dp[node]){
cnt++;
timp[cnt].first = ++stamp;
comp[node] = cnt;
}else{
comp[node] = comp[p]; ///nu cnttt ca se modifica
}
for(auto x : v[node]){
if(!comp[x]){
assignComp(x, node);
}
}
timp[comp[node]].second = stamp;
}
pii special[NMAX];
pii edges[NMAX];
void calc(int node, int p){
viz[node] = 1;
for(auto x : v[node]){
if(!viz[x]){
calc(x, node);
if(comp[node] != comp[x]){
surse[comp[node]] += surse[comp[x]];
deste[comp[node]] += deste[comp[x]];
}
}
}
}
int main() {
int i;
/// Poate sunt mai multe componente
cin >> n >> m;
for(i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
edges[i] = {x, y};
}
for(i = 1; i <= n; i++)
if(!lvl[i])
DFS(i, 0);
for(i = 1; i <= n; i++)
if(!comp[i])
assignComp(i, 0);
int q;
cin >> q;
for(i = 1; i <= q; i++){
int x, y;
cin >> x >> y;
special[i] = {x, y};
if(comp[x] == comp[y])
continue;
if(par(comp[x], comp[y])){
deste[comp[y]]++;
///se termina de adunat la
deste[comp[x]]--;
continue;
}
if(par(comp[y], comp[x])){
surse[comp[x]]++;
///se termina de adunat la
surse[comp[y]]--;
continue;
}
surse[comp[x]]++;
deste[comp[y]]++;
}
for(i = 1; i <= n; i++){
if(!viz[i])
calc(i, 0);
}
for(i = 1; i <= m; i++){
int x = edges[i].first;
int y = edges[i].second;
if(lvl[x] > lvl[y]){
swap(x, y);
}
if(parent[y] != x){
cout << "B";
continue;
}
if(dp[y] != 0){
cout << "B";
continue;
}
if(!deste[comp[y]] && !surse[comp[y]]){
cout << "B";
continue;
}
if(surse[comp[y]] > 0){
if(y == edges[i].first){
cout << "R";
}else{
cout << "L";
}
continue;
}
if(y == edges[i].first){
cout << "L";
}else{
cout << "R";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
