#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector<int> adj[MAXN+1];
map<pair<int,int>, int> edge;
map<pair<int,int>, char> ans;
int dep[MAXN+1], low[MAXN+1], cntX[MAXN+1], cntY[MAXN+1];
void dfs(int v, int p) {
dep[v] = low[v] = dep[p] + 1;
for (int u : adj[v]) {
if (u == p || u == v) continue;
if (dep[u] == 0) {
dfs(u, v);
low[v] = min(low[v], low[u]);
cntX[v] += cntX[u];
cntY[v] += cntY[u];
} else {
low[v] = min(low[v], dep[u]);
}
}
int node1 = v, node2 = p;
if (cntX[v] == cntY[v] || dep[v] != low[v] || edge[{v,p}] + edge[{p,v}] != 1) return;
if (edge.find({v, p}) == edge.end()) swap(node1, node2);
pair<int,int> orient;
if (cntX[v] > cntY[v]) {
// edge should go from v -> p
orient = {v, p};
} else {
orient = {p, v};
}
if (orient == make_pair(node1, node2)) {
ans[{node1, node2}] = 'R';
} else {
ans[{node1, node2}] = 'L';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m; cin >> n >> m;
pair<int,int> graph[m];
for (int i = 0; i < m; i++) {
int a,b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
edge[{a,b}]++;
edge[{b, a}]++;
graph[i] = {a, b};
}
int p; cin >> p;
while (p--) {
int x,y; cin >> x >> y;
cntX[x]++, cntY[y]++;
}
for (int v = 1; v <= n; v++) {
if (dep[v] == 0) {
dfs(v,0);
}
}
for (auto [a,b] : graph) {
cout << (!ans.count({a,b}) ? 'B' : ans[{a,b}]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
