#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
using namespace std;
using PII = pair <int, int>;
struct Edge {
int a, b, id;
bool operator < (const Edge& x) const {
return mp(a, b) < mp(x.a, x.b);
}
};
const int N = 1e5+5;
vector <PII> paths[N];
vector <Edge> edges;
int n, m, k, q, curT;
int vis[N], dp[N];
int par[N];
int find(int a) {
if (par[a] == a) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
par[b] = a;
}
stack <int> stk;
int dfs(int pos, int p = -1) {
vis[pos] = ++curT;
// cout << pos << '\n';
int got = 0;
for (auto& [a, b] : paths[pos]) {
if (b == p || vis[a] > vis[pos]) continue;
if (vis[a] > 0 && vis[a] < vis[pos]) {
dp[pos]++;
dp[a]--;
continue;
}
got += dfs(a, b);
}
// cout << "VAL: " << pos << ' ' << dp[pos]+got << '\n';
if (dp[pos]+got > 0) stk.push(pos);
if (!stk.empty() && got > 0 && got+dp[pos]==0) {
int cur = pos;
while(!stk.empty()) {
int x = stk.top(); stk.pop();
merge(cur, x);
}
}
dp[pos] += got;
return dp[pos];
}
string answ = "XLRB";
int ans[N]; // 1 L, 2 R, 3 B
map <PII, int> ids;
bool vis1[N];
int dfs1(int pos, int par = 0) {
if (vis1[pos]) return 0;
vis1[pos] = 1;
// cout << pos << ' ' << par << '\n';
for (auto& [a, b] : paths[pos]) {
if (a == par) continue;
if (find(a) == find(pos)) dfs1(a, pos);
else dp[pos] += dfs1(a, pos);
}
if (par > 0) {
// cout << pos << ' ' << par << '\n';
// cout << pos << ',' << par << ' ' << dp[pos] << '\n';
if (dp[pos] > 0) {
if (ids.count({pos, par})) ans[ids[{pos, par}]] |= 2;
else ans[ids[{par, pos}]] |= 1;
// cout << ans[ids[{pos, par}]] << '\n';
} else if (dp[pos] == 0) {
if (ids.count({pos, par})) ans[ids[{pos, par}]] |= 3;
else ans[ids[{par, pos}]] |= 3;
} else {
if (ids.count({pos, par})) ans[ids[{pos, par}]] |= 1;
else ans[ids[{par, pos}]] |= 2;
}
}
return dp[pos];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b;
if (a == b) {
ans[i] |= 3;
} else {
edges.pb({a, b, i});
paths[a].pb({b, i});
paths[b].pb({a, i});
}
ids[{a, b}] = i;
// ids[{b, a}] = i;
}
// find and merge cycles
{
iota(par+1, par+1+n, 1);
dfs(1);
// for (int i = 1; i <= n; i++) {
// cout << i << ": " << find(i) << '\n';
// }
}
memset(dp, 0, sizeof(dp));
cin >> q;
for (int i = 1; i <= q; i++) {
int a, b; cin >> a >> b;
dp[a]++; dp[b]--;
// cout << "HELLO: " << a << ' ' << b << '\n';
}
for (int i = 1; i <= n; i++) {
int x = find(i);
if (x == i) continue;
for (auto el : paths[i]) paths[x].pb(el);
}
dfs1(find(1));
for (auto edge : edges) {
if (find(edge.a) == find(edge.b)) ans[edge.id] |= 3;
}
for (int i = 1; i <= m; i++) cout << answ[ans[i]];
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
