Submission #1074844

#TimeUsernameProblemLanguageResultExecution timeMemory
1074844pqthangvOne-Way Streets (CEOI17_oneway)C++11
0 / 100
2 ms4960 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9 + 5; const ll oo = 1e18 + 5; const int MAXN = 1e5 + 5; const int LOG = 16; //#define int ll int n, m, TimerDFS, low[MAXN], num[MAXN], scc_quanity, scc_id[MAXN], par[MAXN][LOG + 1]; int high[MAXN], f[MAXN]; pair<int, int> edges[MAXN]; vector<pair<int, int>> adj[MAXN]; vector<int> g[MAXN]; bool del[MAXN]; stack<int> st; void DFS_tarjan(int u, int pid) { ++TimerDFS; st.push(u); // cout << u << '\n'; num[u] = low[u] = TimerDFS; for (int i = 0; i < int(adj[u].size()); ++i) { int v = adj[u][i].first, nid = adj[u][i].second; if (pid != nid && del[v] == false){ if (num[v] == 0) { DFS_tarjan(v, nid); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], num[v]); } } if (low[u] == num[u]) { int v; ++scc_quanity; do { v = st.top(); del[v] = true; st.pop(); scc_id[v] = scc_quanity; } while (v != u); } } void DFS_high(int u, int p) { for (int i = 0; i < int(g[u].size()); ++i) { int v = g[u][i]; if (v != p) { high[v] = high[u] + 1; par[v][0] = u; DFS_high(v, u); } } } void prepare_LCA() { high[0] = -1; DFS_high(1, -1); for (int j = 1; j <= LOG; ++j) { for (int i = 1; i <= n; ++i) { par[i][j] = par[par[i][j - 1]][j - 1]; } } } int LCA(int u, int v) { if (high[u] < high[v]) return LCA(v, u); int k = high[u] - high[v]; for (int i = 0; i <= LOG; ++i) { if ((k >> i) & 1) { u = par[u][i]; } } if (u == v) return u; for (int i = LOG; i >= 0; --i) { if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } } return par[u][0]; } void DFS_solve(int u, int p) { for (int i = 0; i < int(g[u].size()); ++i) { int v = g[u][i]; if (v != p) { DFS_solve(v, u); f[u] += f[v]; } } } void solve() { cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; adj[u].push_back({v, i}); adj[v].push_back({u, i}); edges[i] = {u, v}; } for (int i = 1; i <= n; ++i) if (num[i] == 0) DFS_tarjan(i, -1); // cout << TimerDFS << '\n'; // cout << scc_quanity << '\n'; // for (int i = 1; i <= n; ++i) { // cout << scc_id[i] << ' '; // } // cout << '\n'; for (int i = 1; i <= m; ++i) { int u = scc_id[edges[i].first], v = scc_id[edges[i].second]; // vi la vo huong nen ko co canh trung if (u != v) { g[u].push_back(v); g[v].push_back(u); } } // for (int i = 1; i <= scc) prepare_LCA(); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; u = scc_id[u]; v = scc_id[v]; int uv = LCA(u, v); ++f[u]; f[v] += 2; f[uv] -= 3; } DFS_solve(1, -1); for (int i = 1; i <= m; ++i) { int u = scc_id[edges[i].first], v = scc_id[edges[i].second]; // cout << u << ' ' << v << ' ' << high[u] << ' ' << high[v] << ' '; if (u == v) { cout << "B"; } else { if (high[u] > high[v]) { if (f[u] == 1) cout << "R"; else cout << "L"; } else if (f[v] == 1) cout << "L"; else cout << "R"; } // cout << '\n'; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // freopen("phanluong.inp", "r", stdin); // freopen("phanluong.out", "w", stdout); // int T = 1; cin >> T; while(T--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...