제출 #994470

#제출 시각아이디문제언어결과실행 시간메모리
994470vladiliusOne-Way Streets (CEOI17_oneway)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define ins insert struct TR{ vector<vector<int>> g; vector<pii> ed; int n; TR(int ns){ n = ns; g.resize(n + 1); } void add(int u, int v){ ed.pb({u, v}); g[u].pb(v); g[v].pb(u); } vector<int> sz, h, p, d; void fill(int v, int pr){ p[v] = pr; sz[v] = 1; for (int i: g[v]){ if (i == pr) continue; d[i] = d[v] + 1; fill(i, v); if (sz[i] > sz[h[v]]){ h[v] = i; } sz[v] += sz[i]; } } vector<int> hd, pos; int cnt; void fill_hld(int v, int k){ pos[v] = ++cnt; hd[v] = k; if (!h[v]) return; fill_hld(h[v], k); for (int i: g[v]){ if (i != p[v] && i != h[v]){ fill_hld(i, i); } } } vector<int> f, inv; vector<bool> b; set<int> st; void build(){ sz.resize(n + 1); h.resize(n + 1); p.resize(n + 1); d.resize(n + 1); fill(1, 0); cnt = 0; hd.resize(n + 1); pos.resize(n + 1); fill_hld(1, 1); inv.resize(n + 1); for (int i = 1; i <= n; i++){ inv[pos[i]] = i; } f.resize(n + 1); for (int i = 2; i <= n; i++) st.ins(i); b.resize(n + 1); for (auto [x, y]: ed){ // x -> y if (d[x] > d[y]){ b[x] = 1; } else { b[y] = 0; } } } int lca(int x, int y){ while (hd[x] != hd[y]){ if (d[hd[x]] > d[hd[y]]){ swap(x, y); } y = p[hd[y]]; } return ((d[x] > d[y]) ? y : x); } void upd(int l, int r, bool i){ if (l > r) return; // cout<<"Yo "<<l<<" "<<b[l]<<" "<<i<<"\n"; auto it = st.lower_bound(l); vector<int> er; while (it != st.end() && *it <= r){ er.pb(*it++); } for (int j: er) st.erase(j); for (int j: er){ // cout<<"Cool "<<inv[j]<<" "<<1 + (b[j] ^ i)<<"\n"; f[inv[j]] = 1 + (b[j] ^ i); } } void set_r(int x, int l, bool i){ // cout<<"Hi "<<x<<" "<<l<<" "<<i<<"\n"; while (true){ if (d[l] < d[hd[x]]){ // hd[x] -> x // x -> ... -> hd[x] upd(pos[hd[x]], pos[x], i); x = p[hd[x]]; } else { // l -> x upd(pos[l] + 1, pos[x], i); break; } } } void setp(int x, int y){ int l = lca(x, y); set_r(x, l, 0); set_r(y, l, 1); } char get(int x, int y){ if (d[x] > d[y]) swap(x, y); if (!f[y]) return 'B'; return ((f[y] == 1) ? 'L' : 'R'); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; vector<pii> g[n + 1], ed; for (int i = 1; i <= m; i++){ int u, v; cin>>u>>v; ed.pb({u, v}); if (u == v) continue; g[u].pb({v, i}); g[v].pb({u, i}); } vector<bool> used(n + 1); vector<int> t[n + 1], ind(n + 1); function<void(int)> dfs = [&](int v){ used[v] = 1; for (auto p: g[v]){ int i = p.ff; if (used[i]) continue; t[i].pb(v); t[v].pb(i); ind[i] = p.ss; dfs(i); } }; for (int i = 1; i <= n; i++){ if (!used[i]){ dfs(i); } } vector<int> d(n + 1, -1), par(n + 1); function<void(int, int)> fill_d = [&](int v, int pr){ par[v] = pr; for (int i: t[v]){ if (i == pr) continue; d[i] = d[v] + 1; fill_d(i, v); } }; for (int i = 1; i <= n; i++){ if (d[i] == -1){ fill_d(i, 0); } } vector<int> dp(n + 1, -1); vector<pii> br; vector<bool> ban(m + 1); function<void(int, int)> solve = [&](int v, int pr){ dp[v] = 0; for (auto p: g[v]){ int i = p.ff; if (i == pr || v == par[i]) continue; dp[v] += (2 * (d[i] < d[v]) - 1); } for (int i: t[v]){ if (i == pr) continue; solve(i, v); dp[v] += dp[i]; } if (!dp[v]){ ban[ind[v]] = 1; if (v != 1) br.pb({v, pr}); } }; for (int i = 1; i <= n; i++){ if (dp[i] == -1){ solve(i, 0); } } fill(used.begin(), used.end(), 0); vector<int> all[n + 1], gr(n + 1); int cnt = 0; function<void(int)> dfs1 = [&](int v){ all[cnt].pb(v); gr[v] = cnt; used[v] = 1; for (auto [i, ii]: g[v]){ if (used[i] || ban[ii]) continue; dfs1(i); } }; for (int i = 1; i <= n; i++){ if (!used[i]){ cnt++; dfs1(i); } } /* cout<<"hey"<<"\n"; for (int i = 1; i <= cnt; i++){ for (int j: all[i]){ cout<<j<<" "; } cout<<"\n"; } cout<<"hey"<<"\n"; */ TR T(cnt); for (auto [x, y]: br){ x = gr[x]; y = gr[y]; T.add(x, y); } T.build(); int q; cin>>q; for (int i = 1; i <= q; i++){ int x, y; cin>>x>>y; x = gr[x]; y = gr[y]; if (x != y) T.setp(x, y); } for (auto [x, y]: ed){ x = gr[x]; y = gr[y]; if (x == y){ cout<<'B'; continue; } // cout<<'T'; cout<<T.get(x, y); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...