Submission #118369

#TimeUsernameProblemLanguageResultExecution timeMemory
118369teomrnOne-Way Streets (CEOI17_oneway)C++14
0 / 100
7 ms5376 KiB
#include <bits/stdc++.h> using namespace std; const int NMAX = 100010; const int LGMAX = 20; namespace UF { int tata[NMAX], g[NMAX]; int find(int x) { if (tata[tata[x]] != tata[x]) tata[x] = find(tata[x]); return tata[x]; } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return 0; if (g[a] < g[b]) swap(a, b); tata[b] = a, g[a] += g[b]; return 1; } void UF(int n) { fill(g, g + n + 1, 1); iota(tata, tata + n + 1, 0); } } bool in_cicle[NMAX]; char ans[NMAX]; vector <pair <int, int>> adia[NMAX]; int muchie_tata[NMAX]; int stramos[LGMAX][NMAX]; int h[NMAX]; int lazy[LGMAX][NMAX]; // for push: 0->nimic, 1->vreau in sus, 2->vreau in jos, 4->sunt in ciclu void dfs(int nod, int tata) { stramos[0][nod] = tata; h[nod] = 1 + h[tata]; for (int i = 1; i < LGMAX; i++) stramos[i][nod] = stramos[i - 1][stramos[i - 1][nod]]; for (auto i : adia[nod]) { if (i.first == tata) muchie_tata[nod] = i.second; else dfs(i.first, nod); } } int lca(int a, int b) { if (h[a] < h[b]) swap(a, b); for (int i = LGMAX - 1; i >= 0; i--) if (h[a] - (1 << i) >= h[b]) a = stramos[i][a]; if (a == b) return a; for (int i = LGMAX - 1; i >= 0; i--) if (stramos[i][a] != stramos[i][b]) a = stramos[i][a], b = stramos[i][b]; return stramos[0][a]; } void push_on_chain(int from, int to, int val) { /// to este NEAPARAT stramos de-al lui from int l = h[from] - h[to]; for (int i = LGMAX - 1; i >= 0; i--) { if (l >= (1 << i)) { lazy[i][from] |= val; from = stramos[i][from]; l -= (1 << i); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, a, b; cin >> n >> m; UF::UF(n); vector <pair <int, int>> useless; for (int i = 1; i <= m; i++) { cin >> a >> b; if (!UF::unite(a, b)) { /// am un ciclu useless.push_back({ a, b }); in_cicle[i] = 1; ans[i] = 'B'; } else { adia[a].push_back({ b, i }); adia[b].push_back({ a, -i }); } } assert(UF::g[UF::find(1)] == n); dfs(1, 0); for (auto i : useless) { int l = lca(i.first, i.second); push_on_chain(i.first, l, 4); push_on_chain(i.second, l, 4); } int q; cin >> q; while (q--) { cin >> a >> b; /// vreau sa ma duc de la a la b int l = lca(a, b); push_on_chain(a, l, 1); push_on_chain(b, l, 2); } for (int i = LGMAX - 1; i; i--) { for (int j = 1; j <= n; j++) { lazy[i - 1][j] |= lazy[i][j]; lazy[i - 1][stramos[i - 1][j]] |= lazy[i][j]; } } for (int i = 2; i <= n; i++) { bool sus = (lazy[0][i] & 1); bool jos = (lazy[0][i] & 2); int id = muchie_tata[i]; int rev = (id < 0); id = abs(id); in_cicle[id] = (lazy[0][i] & 4); if (in_cicle[id]) ans[id] = 'B'; else { assert(!sus || !jos); if (sus) ans[id] = "RL"[rev]; else if (jos) ans[id] = "LR"[rev]; else ans[id] = 'B'; } } for (int i = 1; i <= m; i++) cout << ans[i]; cout << '\n'; return 0; }/* 5 6 1 2 1 2 4 3 2 3 1 3 5 1 2 4 5 1 3*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...