// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
struct DSU {
vi e; void init(int N) { e = vi(N, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool unite(int x, int y) {
x = get(x), y = get(y); if (x == y) return 0;
e[x] += e[y]; e[y] = x; return 1;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; cin >> N >> M;
DSU D; D.init(N);
V<V<pi>> adj(N); V<pi> ex, E;
string ans(M, 'B');
for(int i = 0; i < M; i++) {
int u, v; cin >> u >> v; --u, --v;
E.pb(mp(u, v));
if (D.unite(u, v)) adj[u].pb(mp(v, i)), adj[v].pb(mp(u, i));
else ex.pb(mp(u, v));
}
V<pi> par(N); vi dep(N);
function<void(int)> dfs = [&](int u) {
for(auto& v : adj[u]) if (v.f != par[u].f) {
par[v.f] = mp(u, v.s); dep[v.f] = dep[u] + 1; dfs(v.f);
}
};
par[0] = mp(-1, -1); dep[0] = 0; dfs(0);
D.init(N);
for(auto& p : ex) {
auto [u, v] = p;
while(1) {
int a = D.get(u), b = D.get(v);
if (a == b) break;
if (dep[a] < dep[b]) swap(a, b);
D.unite(par[a].f, a);
}
}
// V<V<pi>> ADJ(N);
// for(int u = 0; u < N; u++) for(auto& v : adj[u]) if (D.get(v.f) != D.get(u)) {
// int a = D.get(u), b = D.get(v.f);
// ADJ[a].pb(mp(b, v.s));
// }
// adj.swap(ADJ);
// par[0] = mp(-1, -1); dep[0] = 0; dfs(0);
assert(false);
vi to(M, -1);
int Q; cin >> Q;
for(int i = 0; i < Q; i++) {
int u, v; cin >> u >> v; --u, --v;
if (D.get(u) == D.get(v)) continue;
// cout << u << " " << v << endl;
while(1) {
int a = D.get(u), b = D.get(v);
// cout << u << " " << v << endl;
// cout << a << " " << b << endl;
if (a == b) break;
if (dep[a] < dep[b]) swap(a, b);
// cout << D.get(u) << " -> " << a << endl;
// change label of edge
to[par[a].s] = (D.get(u) == a ? par[a].f : a);
assert(par[a].f != -1); D.unite(par[a].f, a);
}
}
for(int i = 0; i < M; i++) if (to[i] != -1) {
// cout << to[i] << endl;
ans[i] = (E[i].f == to[i] ? 'L' : 'R');
}
cout << ans << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3074 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3074 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3074 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
