#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 100;
vector<vector<int>> graph, G, G_rev;
vector<vector<pair<int,int>>> G2;
int mark[MAXN], a[MAXN], b[MAXN], vis[MAXN], par[MAXN], sz[MAXN], ways[MAXN];
int find(int node) {
if (node == par[node])
return node;
return par[node] = find(par[node]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return ;
if (sz[b] > sz[a])
swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
void dfs(int node, int parent) {
vis[node] = 1;
for (auto u : graph[node]) {
if (u != parent && vis[u] != 2) {
G[node].push_back(u);
G_rev[u].push_back(node);
}
if (!vis[u])
dfs(u, node);
}
vis[node] = 2;
}
stack<int> nds;
void dfs2(int node) {
vis[node] = true;
for (auto u : G[node]) {
if (!vis[u])
dfs2(u);
}
nds.push(node);
}
void dfs3(int node) {
vis[node] = true;
for (auto u : G_rev[node]) {
if (vis[u])
continue;
unite(node, u);
dfs3(u);
}
}
void dfs4(int node) {
vis[node] = true;
for (auto u : G2[node]) {
if (vis[u.f])
continue;
dfs4(u.f);
mark[node] += mark[u.f];
if (a[u.s] == node) {
if (mark[u.f] > 0)
ways[u.s] = 1;
else
ways[u.s] = 2;
} else { // b[u.s] == node
if (mark[u.f] > 0)
ways[u.s] = 2;
else
ways[u.s] = 1;
}
}
}
map<pair<int,int>,int> mp;
int main() {
fast
int n, m, q;
cin >> n >> m;
for (int i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
graph = vector<vector<int>>(n+1, vector<int>());
G = vector<vector<int>>(n+1, vector<int>());
G2 = vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>());
G_rev = vector<vector<int>>(n+1, vector<int>());
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
mp[{min(a[i], b[i]), max(a[i], b[i])}]++;
graph[a[i]].push_back(b[i]);
graph[b[i]].push_back(a[i]);
}
for (int i = 1; i <= n; i++) {
if (!vis[i])
dfs(i, i);
}
for (int i = 1; i <= n; i++)
vis[i] = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i])
dfs2(i);
}
for (int i = 1; i <= n; i++)
vis[i] = 0;
while (nds.size()) {
int node = nds.top();
nds.pop();
if (!vis[node])
dfs3(node);
}
for (int i = 1; i <= m; i++) {
if (find(a[i]) == find(b[i]))
ways[i] = -1;
else {
G2[find(a[i])].push_back({find(b[i]), i});
G2[find(b[i])].push_back({find(a[i]), i});
}
}
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
a = find(a);
b = find(b);
if (a == b)
continue;
mark[b] -= 1;
mark[a] += 1;
}
for (int i = 1; i <= n; i++)
vis[i] = false;
for (int i = 1; i <= n; i++) {
if (!vis[find(i)])
dfs4(find(i));
}
for (int i = 1; i <= m; i++) {
if (mp[{min(a[i], b[i]), max(a[i], b[i])}] > 1 || a[i] == b[i])
cout << "B";
else if (ways[i] == 1)
cout << "L";
else if (ways[i] == 2)
cout << "R";
else
cout << "B";
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
