제출 #853591

#제출 시각아이디문제언어결과실행 시간메모리
853591mbfibatOne-Way Streets (CEOI17_oneway)C++17
0 / 100
2 ms10840 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; const int N = 1e5 + 11; int n, m; char ans[N]; ii org_edge[N]; vector<int> adj[N]; map<ii, int> dir, org, cnt; int height[N], lca[N][21]; int top = 0; int cur[N], low[N]; map<ii, bool> is_bridge; void dfs(int u, int p = 0) { cur[u] = low[u] = ++top; for (int v : adj[u]) { if (!cur[v]) { dfs(v, u); low[u] = min(low[u], low[v]); // cerr << u << ' ' << v << ' ' << low[v] << ' ' << cur[u] << '\n'; if (low[v] > cur[u]) { is_bridge[ii(u, v)] = is_bridge[ii(v, u)] = (cnt[ii(u, v)] == 1); cerr << u << ' ' << v << ' ' << is_bridge[ii(u, v)] << '\n'; } } else if (v != p) low[u] = min(low[u], cur[v]); } } int id[N]; ii upd[N], par[N]; vector<ii> adj_compress[N]; void compress(int u) { id[u] = top; for (int v : adj[u]) { if (id[v]) { if (id[v] != top) { adj_compress[id[u]].emplace_back(id[v], org[ii(u, v)]); adj_compress[id[v]].emplace_back(id[u], org[ii(u, v)]); } continue; } if (is_bridge[ii(u, v)]) continue; compress(v); } } void dfs2(int u, int p = -1) { for (int j = 1; j <= 20; j++) lca[u][j] = lca[lca[u][j - 1]][j - 1]; for (auto [v, edge_id] : adj_compress[u]) { if (v == p) continue; height[v] = height[u] + 1; lca[v][0] = u; par[v] = ii(u, edge_id); dfs2(v, u); } } void upd_go(int u, int v, int edge_id) { if (dir[ii(u, v)]) ans[edge_id] = 'R'; else ans[edge_id] = 'L'; } int cal_lca(int u, int v) { if (height[u] > height[v]) swap(u, v); for (int j = 20; j >= 0; j--) if (height[lca[v][j]] > height[u]) v = lca[v][j]; if (u == v) return u; for (int j = 20; j >= 0; j--) if (lca[u][j] != lca[v][j]) { u = lca[u][j]; v = lca[v][j]; } return lca[u][0]; } int main(int argc, char** argv) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); dir[ii(u, v)] = true; org_edge[i] = ii(u, v); cnt[ii(u, v)]++; cnt[ii(v, u)]++; org[ii(u, v)] = org[ii(v, u)] = i; } for (int i = 1; i <= n; i++) if (!cur[i]) dfs(i); cerr << "--------------------------------" << '\n'; top = 0; height[1] = 1; for (int i = 1; i <= n; i++) if (!id[i]) { ++top; compress(i); } for (int i = 1; i <= top; i++) cur[i] = 0; for (int i = 1; i <= top; i++) if (!cur[i]) dfs2(i); cerr << "--------------------------------" << '\n'; for (int i = 1; i <= top; i++) upd[i] = ii(1e9, 0); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; u = id[u], v = id[v]; int p = cal_lca(u, v); upd[u] = min(upd[u], ii(height[p], 0)); upd[v] = min(upd[v], ii(height[p], 1)); } cerr << "--------------------------------" << '\n'; vector<ii> ord; for (int i = 1; i <= top; i++) ord.emplace_back(height[i], i); for (int i = 1; i <= m; i++) ans[i] = 'B'; sort(ord.begin(), ord.end()); for (auto [_, u] : ord) { if (upd[u].first >= height[u]) continue; auto [cur_h, type] = upd[u]; auto [p, edge_id] = par[u]; upd[p] = min(upd[p], upd[u]); if (!type) upd_go(u, p, edge_id); else upd_go(p, u, edge_id); } for (int i = 1; i <= m; i++) cout << ans[i]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...