Submission #679835

#TimeUsernameProblemLanguageResultExecution timeMemory
679835peijarOne-Way Streets (CEOI17_oneway)C++17
0 / 100
3 ms2772 KiB
#include <bits/stdc++.h> #define int long long using namespace std; namespace std { template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) { out << "["; for (int i = 0; i < (int)vec.size(); ++i) { out << vec[i]; if (i + 1 < (int)vec.size()) out << ", "; } return out << "]"; } } // namespace std void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif const int MAXN = 1e5; struct UnionFind { vector<int> id; UnionFind() {} UnionFind(int N) { id.assign(N, -1); } int find(int u) { if (id[u] < 0) return u; return id[u] = find(id[u]); } bool merge(int u, int v) { u = find(u), v = find(v); if (u == v) return false; if (id[u] > id[v]) swap(u, v); id[u] += id[v]; id[v] = u; return true; } }; vector<pair<int, int>> adj[MAXN]; vector<pair<int, int>> edges; vector<int> num, st; int Time; vector<int> bridges; bool isBridge[MAXN]; int dfs(int at, int par) { int me = num[at] = ++Time, e, y, top = me; for (auto pa : adj[at]) if (pa.second != par) { tie(y, e) = pa; if (num[y]) top = min(top, num[y]); else { int up = dfs(y, e); top = min(top, up); if (up == me) { } else if (up < me) { } else { bridges.push_back(e); isBridge[e] = true; } } } return top; } void bicomps() { num.assign(edges.size(), 0); for (int i = 0; i < (int)edges.size(); ++i) if (!num[i]) dfs(i, -1); } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbSommet, nbAretes, nbRequetes; cin >> nbSommet >> nbAretes; edges.resize(nbAretes); for (int i = 0; i < nbAretes; ++i) { auto &[u, v] = edges[i]; cin >> u >> v; --u, --v; adj[u].emplace_back(v, i); adj[v].emplace_back(u, i); } cin >> nbRequetes; vector<pair<int, int>> queries(nbRequetes); for (auto &[u, v] : queries) { cin >> u >> v; --u, --v; } bicomps(); UnionFind dsu(nbSommet); for (int i = 0; i < nbAretes; ++i) if (!isBridge[i]) dsu.merge(edges[i].first, edges[i].second); vector<int> roots; for (int u = 0; u < nbSommet; ++u) if (dsu.find(u) == u) roots.push_back(u); auto getId = [&](int u) { return lower_bound(roots.begin(), roots.end(), dsu.find(u)) - roots.begin(); }; for (int u = 0; u < nbSommet; ++u) adj[u].clear(); for (int iArete = 0; iArete < nbAretes; ++iArete) { if (isBridge[iArete]) { auto [u, v] = edges[iArete]; u = getId(u); v = getId(v); if (u == v) continue; adj[u].emplace_back(v, iArete); adj[v].emplace_back(u, iArete); } } int nbRoots = roots.size(); vector<int> cntDeb(nbRoots), cntFin(nbRoots); for (auto [u, v] : queries) { u = getId(u); v = getId(v); if (u == v) continue; cntDeb[u]++; cntFin[v]++; } vector<int> side(nbAretes); vector<bool> seen(nbRoots); auto dfsBridge = [&](auto rec, int u, int p) -> void { seen[u] = true; for (auto [v, id] : adj[u]) if (v != p) { rec(rec, v, u); cntDeb[u] += cntDeb[v]; cntFin[u] += cntFin[v]; if (cntDeb[v] > cntFin[v]) { side[id] = getId(edges[id].first) == u ? -1 : 1; } if (cntFin[v] > cntDeb[v]) side[id] = getId(edges[id].first) == u ? 1 : -1; } }; for (int u = 0; u < nbRoots; ++u) if (!seen[u]) dfsBridge(dfsBridge, u, u); for (int x : side) { if (x == 0) cout << 'B'; else if (x == -1) cout << 'L'; else cout << 'R'; } cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...