//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
struct edge {
int a, b;
};
const int N = 1001000;
int n, m, q, a, b, l;
vector<int> dp, sss, odw, gle, odp, stp, pd;
vector<edge> kr;
vector<vector<int>> v;
vector<vector<pair<int, int>>> vv;
void dfs_gle(int x) {
odw[x] = l;
for (int i : v[x]) {
if (odw[i] < l) {
gle[i] = gle[x] + 1;
dfs_gle(i);
}
}
}
void dfs_dp(int x) {
odw[x] = l;
for (int i : v[x]) {
if (odw[i] < l) {
dfs_dp(i);
dp[x] += dp[i];
}
}
}
void dfs_sss(int x) {
odw[x] = l;
for (int i : v[x]) {
if (odw[i] < l) {
if (dp[i] > 1) {
sss[i] = sss[x];
}
dfs_sss(i);
}
}
}
void get(int &a) {
a = 0;
int g = getchar_unlocked();
while (g < '0' || '9' < g) {
g = getchar_unlocked();
}
while ('0' <= g && g <= '9') {
a = (a << 3) + (a << 1) + g - '0';
g = getchar_unlocked();
}
}
int main() {
get(n);
get(m);
v.resize(n + 1);
odw.resize(n + 1);
gle.resize(n + 1);
sss.resize(n + 1);
stp.resize(n + 1);
pd.resize(n + 1);
vv.resize(n + 1);
kr.resize(m + 1);
for (int i = 1; i <= m; ++i) {
get(a);
get(b);
v[a].push_back(b);
v[b].push_back(a);
kr[i].a = a;
kr[i].b = b;
}
++l;
for (int i = 1; i <= n; ++i) {
if (odw[i] < l) {
dfs_gle(i);
}
}
for (int i = 1; i <= m; ++i) {
if (gle[kr[i].a] > gle[kr[i].b]) {
odp[i] = 1;
swap(kr[i].a, kr[i].b);
}
++dp[kr[i].b];
--dp[kr[i].a];
}
++l;
for (int i = 1; i <= n; ++i) {
if (odw[i] < l) {
dfs_dp(i);
}
sss[i] = i;
}
++l;
for (int i = 1; i <= n; ++i) {
if (odw[i] < l) {
dfs_sss(i);
}
}
for (int i = 1; i <= m; ++i) {
if (sss[kr[i].a] == sss[kr[i].b]) {
odp[i] = 2;
}
else {
vv[sss[kr[i].a]].push_back({sss[kr[i].b], i});
vv[sss[kr[i].b]].push_back({sss[kr[i].a], i});
++stp[sss[kr[i].a]];
++stp[sss[kr[i].b]];
}
}
get(q);
for (int i = 1; i <= q; ++i) {
get(a);
get(b);
++pd[sss[a]];
--pd[sss[b]];
}
queue<int> que;
for (int i = 1; i <= n; ++i) {
if (stp[i] == 1) {
que.push(i);
}
}
++l;
while (!que.empty()) {
int x = que.front();
que.pop();
odw[x] = l;
for (auto i : vv[x]) {
if (odw[i.first] < l) {
--stp[i.first];
if (pd[x] == 0) {
odp[i.second] = 2;
}
else if ((pd[x] > 0) == (x == kr[i.second].b)) {
odp[i.second] ^= 1;
}
pd[i.first] += pd[x];
if (stp[i.first] == 1) {
que.push(i.first);
}
}
}
}
for (int i = 1; i <= m; ++i) {
if (odp[i] == 0) {
printf("R");
}
else if (odp[i] == 1) {
printf("L");
}
else {
printf("B");
}
}
printf("\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
312 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
312 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
312 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
