Submission #1222522

#TimeUsernameProblemLanguageResultExecution timeMemory
1222522radodododoOne-Way Streets (CEOI17_oneway)C++20
30 / 100
3097 ms35612 KiB
#include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; struct reb { long long u, i, a, b; reb(long long u = 0, long long i = 0, long long a = 0, long long b = 0) { this->u = u; this->i = i; this->a = a; this->b = b; } }; long long n, m; vector<vector<reb>> normg; vector<vector<reb>> org; vector<bool> used; vector<bool> doner; vector<long long> topsort; vector<long long> color; long long c = 0; vector<vector<reb>> g; vector<long long> parent; vector<vector<long long>> lift; long long logg = 18; vector<long long> h; long long high = 0; void dfs_newg(long long v) { topsort.push_back(v); used[v] = 1; for (auto r : normg[v]) { if (!doner[r.i]) { doner[r.i] = 1; reb rr(v, r.i, r.a, r.b); org[r.u].push_back(rr); } if (!used[r.u]) { dfs_newg(r.u); } } } void paint(long long v) { color[v] = c; for (auto r : org[v]) { if (color[r.u] == -1) { paint(r.u); } } } void countlca() { lift[0] = parent; for (long long k = 1; k < logg; k++) { for (long long v = 0; v < c; v++) { lift[k][v] = lift[k - 1][lift[k - 1][v]]; } } } long long lca(long long v, long long u) { if (h[v] < h[u]) { swap(v, u); } long long dist = h[v] - h[u]; for (long long k = 0; k < logg; k++) { if ((dist & (1 << k)) != 0) { v = lift[k][v]; } } for (long long k = logg - 1; k >= 0; k--) { if (lift[k][v] != lift[k][u]) { u = lift[k][u]; v = lift[k][v]; } } if (u == v) { return u; } return parent[u]; } vector<long long> s, tin, tout; vector<long long> head; long long timee = 0; void dfs_parent(long long v, long long p) { used[v] = 1; parent[v] = p; s[v] = 1; h[v] = high; high++; for (auto& r : g[v]) { if (r.u == p) { continue; } dfs_parent(r.u, v); s[v] += s[r.u]; if (s[g[v][0].u] < s[r.u]) { swap(g[v][0], r); } } high--; } void hld(long long v, long long p) { tin[v] = timee++; for (auto r : g[v]) { if (r.u == p) { continue; } if (g[v][0].u == r.u) { head[r.u] = head[v]; } else { head[r.u] = r.u; } hld(r.u, v); } tout[v] = timee; } vector<long long> tree; void sett(long long i, long long l, long long r, long long ql, long long qr, long long qx) { if (l == r) { return; } if (r <= ql || qr <= l) { return; } if (ql <= l && r <= qr) { tree[i] = qx; return; } long long mid = (l + r) / 2; sett(2 * i + 1, l, mid, ql, qr, qx); sett(2 * i + 2, mid, r, ql, qr, qx); } long long gett(long long i, long long l, long long r, long long qi) { if (l + 1 == r) { return tree[i]; } if (tree[i] != 0) { return tree[i]; } long long mid = (l + r) / 2; if (qi < mid) { return gett(2 * i + 1, l, mid, qi); } return gett(2 * i + 2, mid, r, qi); } long long pred(long long a, long long b) { return tin[a] <= tin[b] && tin[b] <= tout[a]; } void up(long long a, long long b, long long qx) { while (!pred(head[a], b)) { sett(0, 0, c, tin[head[a]], tin[a] + 1, qx); a = parent[head[a]]; } sett(0, 0, c, tin[b] + 1, tin[a] + 1, qx); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; normg.resize(n); vector<reb> allrebs(m); for (long long i = 0; i < m; i++) { long long a, b; cin >> a >> b; a--, b--; reb ab(b, i, a, b); allrebs[i] = ab; reb ba(a, i, a, b); normg[a].push_back(ab); normg[b].push_back(ba); } used.resize(n); doner.resize(m); org.resize(n); for (long long i = 0; i < n; i++) { if (!used[i]) { dfs_newg(i); } } color.resize(n, -1); for (auto v : topsort) { if (color[v] == -1) { paint(v); c++; } } g.resize(c); for (long long i = 0; i < n; i++) { for (auto r : normg[i]) { if (color[r.a] != color[r.b]) { reb rrr(color[r.u], r.i, r.a, r.b); g[color[i]].push_back(rrr); } } } parent.resize(c); h.resize(c); s.resize(c); tin.resize(c); tout.resize(c); head.resize(c); used.assign(c, 0); for (long long i = 0; i < c; i++) { if (!used[i]) { dfs_parent(i, i); hld(i, i); } } lift.resize(logg, vector<long long>(c)); countlca(); tree.resize(4 * n); long long p; cin >> p; for (long long gh = 0; gh < p; gh++) { long long a, b; cin >> a >> b; a--, b--; a = color[a]; b = color[b]; if (a == b) { continue; } long long l = lca(a, b); if (a != l) { up(a, l, -1); } if (b != l) { up(b, l, 1); } } string anser; for (long long i = 0; i < m; i++) { if (color[allrebs[i].a] == color[allrebs[i].b]) { anser.push_back('B'); continue; } reb r = allrebs[i]; r.a = color[r.a]; r.b = color[r.b]; if (h[r.a] > h[r.b]) { long long val = gett(0, 0, c, tin[r.a]); if (val == -1) { anser.push_back('R'); } else if (val == 1) { anser.push_back('L'); } else { anser.push_back('B'); } } else { long long val = gett(0, 0, c, tin[r.b]); if (val == 1) { anser.push_back('R'); } else if (val == -1) { anser.push_back('L'); } else { anser.push_back('B'); } } } cout << anser; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...