#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (LLONG_MAX/2)
#pragma GCC optimize ("O3")
vector<vector<pair<int, int> > > g, g2;
vector<int> tin, l, comp;
vector<char> elirany;
int t = 1;
int mincomp=1;
void dfs(int v, int p = -1) {
tin[v] = t++;
l[v] = tin[v];
for (auto [u, i] : g[v]) {
if (u != p) {
if (!tin[u]) {
comp[u]=comp[v];
dfs(u, v);
l[v] = min(l[v], l[u]);
if (l[u] > tin[v]) {
mincomp++;
comp[u]=mincomp;
g2[comp[v]].push_back(make_pair(comp[u], i));
g2[comp[u]].push_back(make_pair(comp[v], -i));
}
} else {
l[v] = min(l[v], tin[u]);
}
}
}
}
bool dfs2(int v, int cel, int p=-1) {
if (cel == v) return true;
for (auto [u, i] : g2[v]) {
if (u == p) continue;
if (dfs2(u, cel, v)) {
if (i > 0) {
elirany[i] = 'R';
} else {
elirany[-i] = 'L';
}
return true;
}
}
return false;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
g.resize(n + 1);
tin.resize(n + 1, 0);
l.resize(n + 1, INF);
comp.resize(n + 1);
elirany.resize(m+1,'B');
g2.resize(n + 1);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back({b, i});
g[b].push_back({a, -i});
}
comp[1]=mincomp;
dfs(1);
//for (int i=1; i<=n;i++) cout<<comp[i]<<endl;
int q;
cin >> q;
vector<int> from(q), to(q);
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
a = comp[a];
b = comp[b];
from[i] = a;
to[i] = b;
dfs2(a, b);
}
for (int i=1; i<=m;i++){
cout << elirany[i];
}
cout << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
