Submission #954567

#TimeUsernameProblemLanguageResultExecution timeMemory
954567mochaOne-Way Streets (CEOI17_oneway)C++14
0 / 100
8 ms33624 KiB
#include <bits/stdc++.h> using namespace std; const int mx = 2e5+5; int n, m, q; vector<int> g[mx]; bool vis[mx], vise[mx]; int dfn[mx], low[mx]; int t; int ans[mx]; int p[30][mx]; int pe[mx]; int pp[mx]; int dep[mx]; // R = 1, L = 2, B = 3 struct Edge { int u, v; int id; } e[mx]; void dfs1(int x, int pr, int d, int peg) { dfn[x] = low[x] = ++t; p[0][x] = pr; dep[x] = d; pe[x] = peg; vis[x] = 1; for (int i:g[x]) { if (vise[i]) continue; auto [u, v, id] = e[i]; if (u != x) swap(u, v); if (!vis[v]) { vise[i] = 1; dfs1(v, x, d+1, i); low[u] = min(low[u], low[v]); } else { low[u] = min(dfn[v], low[u]); } } if (low[x] != dfn[x]) { ans[peg] = 3; } } void dfs2(int x, int la) { vis[x] = 1; if (ans[pe[x]] or x == 1) { pp[x] = la; } else { pp[x] = x; } for (int i:g[x]) { auto [u, v, id] = e[i]; if (u != x) swap(u, v); if (vis[v]) continue; dfs2(v, pp[x]); } } void bdlca() { for (int i=1;i<30;i++) { for (int j=1;j<=n;j++) { p[i][j] = p[i-1][p[i-1][j]]; } } } int qlca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int d = dep[u] - dep[v]; for (int i=29;~i;i--) if (d&(1<<i)) u = p[i][u]; if (u == v) return u; for (int i = 29; ~i; i--) { if (p[i][u] != p[i][v]) { u = p[i][u]; v = p[i][v]; } } return p[0][u]; } int main() { // cin.tie(0);ios::sync_with_stdio(0); cin >> n >> m; for (int i=1;i<=m;i++) { int u, v; cin >> u >> v; g[u].push_back(i); g[v].push_back(i); e[i] = {u, v, i}; } dfs1(1, 0, 1, 0); for (int i=1;i<=n;i++) { vis[i] = 0; } dfs2(1, 0); bdlca(); cin >> q; while (q--) { int u, v; cin >> u >> v; int lca = qlca(u, v); vector<int> ve; int lans = 0; while (dep[pp[u]] > dep[lca]) { ve.push_back(pp[u]); ans[pe[pp[u]]] = 1; u = p[0][pp[u]]; lans = pp[u]; } for (int i:ve) { pp[i] = lans; } ve.clear(); while (dep[pp[v]] > dep[lca]) { ve.push_back(pp[v]); ans[pe[pp[v]]] = 2; v = p[0][pp[v]]; lans = pp[v]; } for (int i:ve) { pp[i] = lans; } } for (int i=1;i<=m;i++) { if (ans[i] == 0 or ans[i] == 3) { cout << 'B'; } else if ( ans[i] == 1 ) { if (dep[e[i].u] < dep[e[i].v]) { cout << 'L'; } else { cout << 'R'; } } else { if (dep[e[i].u] < dep[e[i].v] ){ cout << 'R'; } else { cout << 'L'; } } } cout << "\n"; }

Compilation message (stderr)

oneway.cpp: In function 'void dfs1(int, int, int, int)':
oneway.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   auto [u, v, id] = e[i];
      |        ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:54:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   auto [u, v, id] = e[i];
      |        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...