Submission #1222534

#TimeUsernameProblemLanguageResultExecution timeMemory
1222534radodododoOne-Way Streets (CEOI17_oneway)C++20
30 / 100
3096 ms22404 KiB
#include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; struct reb { int u, i, a, b; reb(int u = 0, int i = 0, int a = 0, int b = 0) { this->u = u; this->i = i; this->a = a; this->b = b; } }; int n, m; vector<vector<reb>> normg; vector<vector<reb>> org; bool used[100000]; bool doner[100000]; vector<int> topsort; vector<int> color; int c = 0; vector<vector<reb>> g; int parent[100000]; int lift[18][100000]; int logg = 18; int h[100000]; int high = 0; void dfs_newg(int 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(int v) { color[v] = c; for (auto &r : org[v]) { if (color[r.u] == -1) { paint(r.u); } } } void countlca() { for (long long i = 0; i < c; i++) { lift[0][i] = parent[i]; } for (int k = 1; k < logg; k++) { for (int v = 0; v < c; v++) { lift[k][v] = lift[k - 1][lift[k - 1][v]]; } } } int lca(int v, int u) { if (h[v] < h[u]) { swap(v, u); } int dist = h[v] - h[u]; for (int k = 0; k < logg; k++) { if ((dist & (1 << k)) != 0) { v = lift[k][v]; } } for (int 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<int> s, tin, tout; vector<int> head; int timee = 0; void dfs_parent(int v, int 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(int v, int 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; } int tree[400000]; void sett(int i, int l, int r, int ql, int qr, int qx) { if (l == r) { return; } if (r <= ql || qr <= l) { return; } if (ql <= l && r <= qr) { tree[i] = qx; return; } int mid = (l + r) / 2; sett(2 * i + 1, l, mid, ql, qr, qx); sett(2 * i + 2, mid, r, ql, qr, qx); } int gett(int i, int l, int r, int qi) { if (l + 1 == r) { return tree[i]; } if (tree[i] != 0) { return tree[i]; } int mid = (l + r) >> 1; if (qi < mid) { return gett(2 * i + 1, l, mid, qi); } return gett(2 * i + 2, mid, r, qi); } int pred(int a, int b) { return tin[a] <= tin[b] && tin[b] <= tout[a]; } void up(int a, int b, int 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 (int i = 0; i < m; i++) { int 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); } org.resize(n); for (int 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 (int 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); } } } s.resize(c); tin.resize(c); tout.resize(c); head.resize(c); for (long long i = 0; i < n; i++) { used[i] = 0; } for (int i = 0; i < c; i++) { if (!used[i]) { dfs_parent(i, i); hld(i, i); } } countlca(); int p; cin >> p; for (int gh = 0; gh < p; gh++) { int a, b; cin >> a >> b; a--, b--; a = color[a]; b = color[b]; if (a == b) { continue; } int l = lca(a, b); if (a != l) { up(a, l, -1); } if (b != l) { up(b, l, 1); } } string anser; for (int 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]) { int 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 { int 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...