Submission #927913

#TimeUsernameProblemLanguageResultExecution timeMemory
927913TAhmed33One-Way Streets (CEOI17_oneway)C++98
100 / 100
841 ms79044 KiB
#include <bits/stdc++.h> using namespace std; #define mid ((l + r) >> 1) #define tl (node + 1) #define tr (node + 2 * (mid - l + 1)) const int MAXN = 1e5 + 25; struct SegmentTree { int lazy[2 * MAXN]; int tree[2 * MAXN]; void prop(int l, int r, int node) { if (lazy[node] == -1) return; if (l == r) { tree[node] = lazy[node]; } else { lazy[tl] = lazy[tr] = lazy[node]; } lazy[node] = -1; } void update(int l, int r, int a, int b, int c, int node) { if (l > b || r < a) return; if (l >= a && r <= b) { lazy[node] = c; prop(l, r, node); return; } update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr); } int get(int l, int r, int a, int node) { prop(l, r, node); if (l == r) { return tree[node]; } if (a <= mid) return get(l, mid, a, tl); return get(mid + 1, r, a, tr); } }; SegmentTree cur; set < pair < int, int >> bridges; vector < int > adj1[MAXN]; int in [MAXN], low[MAXN]; bool vis[MAXN]; int t = 0; vector < pair < int, int >> edges; map < pair < int, int > , int > ans; map < pair < int, int > , int > cnt; void dfs(int pos, int par) { vis[pos] = 1; in [pos] = low[pos] = ++t; for (auto j: adj1[pos]) { if (j == par) continue; if (vis[j]) { low[pos] = min(low[pos], in [j]); continue; } dfs(j, pos); low[pos] = min(low[pos], low[j]); if (cnt[{ j, pos }] == 1 && low[j] > in [pos]) { bridges.insert({ pos, j }); } } } struct DSU { int sze[MAXN], par[MAXN]; void init() { for (int i = 1; i < MAXN; i++) { sze[i] = 1; par[i] = i; } } int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); } void merge(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sze[x] > sze[y]) swap(x, y); sze[y] += sze[x]; par[x] = y; } }; DSU comps; vector < pair < int, int >> adj[MAXN]; int p[MAXN]; int sze[MAXN]; int dep[MAXN]; void dfs2(int pos, int par) { p[pos] = par; sze[pos] = 1; vis[pos] = 1; for (int i = 0; i < (int) adj[pos].size(); i++) { if (adj[pos][i].first == par) { adj[pos].erase(adj[pos].begin() + i); break; } } for (auto & j: adj[pos]) { dep[j.first] = 1 + dep[pos]; dfs2(j.first, pos); sze[pos] += sze[j.first]; if (sze[j.first] > sze[adj[pos][0].first]) { swap(j, adj[pos][0]); } } } int in2[MAXN], out2[MAXN], nxt[MAXN]; void dfs3(int pos) { in2[pos] = ++t; for (auto j: adj[pos]) { nxt[j.first] = (j.first == adj[pos][0].first ? nxt[pos] : j.first); dfs3(j.first); } out2[pos] = t; } int uy; map < int, int > xx, xx2; int dp[32][MAXN]; int jump(int a, int b) { for (int i = 23; i >= 0; i--) { if ((b & (1 << i)) && dp[i][a]) a = dp[i][a]; else if (b & (1 << i)) return 0; } return a; } int lca(int a, int b) { if (dep[a] < dep[b]) swap(a, b); int u = dep[a] - dep[b]; a = jump(a, u); if (a == b) return a; for (int i = 23; i >= 0; i--) { int x = dp[i][a], y = dp[i][b]; if (x && y && x != y) a = x, b = y; } return jump(a, 1); } void upd (int a, int b) { while (a) { if (in2[nxt[a]] <= in2[b]) { if (in2[b] < in2[a]) cur.update(1, uy, in2[b] + 1, in2[a], 1, 1); return; } cur.update(1, uy, in2[nxt[a]], in2[a], 1, 1); a = p[nxt[a]]; } } void dow (int a, int b) { while (a) { if (in2[nxt[a]] <= in2[b]) { if (in2[b] < in2[a]) cur.update(1, uy, in2[b] + 1, in2[a], 2, 1); return; } cur.update(1, uy, in2[nxt[a]], in2[a], 2, 1); a = p[nxt[a]]; } } void dfs5 (int pos, int par) { vis[pos] = 1; for (auto j : adj[pos]) { if (j.first != par) { dfs5(j.first, pos); } int x = cur.get(1, uy, in2[j.first], 1); pair <int, int> tt = edges[j.second]; if (x == 0) { ans[tt] = 0; continue; } if (pos == xx[comps.find(tt.second)]) { x = 3 - x; } ans[tt] = x; } } int main() { memset(cur.lazy, -1, sizeof(cur.lazy)); int n, m; cin >> n >> m; comps.init(); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; cnt[{a, b}]++; cnt[{b, a}]++; edges.push_back({a, b}); if (a == b) { ans[{a, b}] = ans[{b, a}] = 0; continue; } if (cnt[{a, b}] > 1) { ans[{a, b}] = ans[{b, a}] = 0; continue; } adj1[a].push_back(b); adj1[b].push_back(a); } for (int i = 1; i <= n; i++) { if (!vis[i]) { dfs(i, 0); } } for (auto[a, b]: edges) { if (!bridges.count({b, a}) && !bridges.count({a, b})) { comps.merge(a, b); ans[{a, b}] = ans[{b, a}] = 0; } } int uu = 0; set < int > pp; for (int i = 1; i <= n; i++) pp.insert(comps.find(i)); uy = pp.size(); for (auto i: pp) { xx[i] = xx.size() + 1; } for (auto i: xx) { xx2[i.second] = i.first; } for (auto[a, b]: edges) { if (bridges.count({b, a}) || bridges.count({a, b})) { adj[xx[comps.find(a)]].push_back({xx[comps.find(b)], uu}); adj[xx[comps.find(b)]].push_back({xx[comps.find(a)], uu}); } uu++; } memset(vis, 0, sizeof(vis)); t = 0; for (int i = 1; i <= uy; i++) { if (!vis[i]) { dfs2(i, 0); nxt[i] = i; dfs3(i); } } for (int i = 1; i <= uy; i++) dp[0][i] = p[i]; for (int i = 1; i <= 23; i++) { for (int j = 1; j <= uy; j++) { dp[i][j] = dp[i - 1][dp[i - 1][j]]; } } /* for (int i = 1; i <= uy; i++) { cout << nxt[i] << " " << p[i] << " " << in2[i] << endl; } cout << "__________\n";*/ int q; cin >> q; while (q--) { int a, b; cin >> a >> b; if (comps.find(a) == comps.find(b)) continue; a = xx[comps.find(a)]; b = xx[comps.find(b)]; int x = lca(a, b); //cout << a << " " << b << " " << x << endl; if (x != a) upd(a, x); if (x != b) dow(b, x); } memset(vis, 0, sizeof(vis)); for (int i = 1; i <= uy; i++) { if (!vis[i]) { dfs5(i, 0); } } for (auto i : edges) { int z = ans[{i.first, i.second}]; if (z == 0) cout << "B"; else if (z == 2) cout << "R"; else cout << "L"; } }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:208:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |   for (auto[a, b]: edges) {
      |            ^
oneway.cpp:224:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  224 |   for (auto[a, b]: edges) {
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...