Submission #1173692

#TimeUsernameProblemLanguageResultExecution timeMemory
1173692buzdiOne-Way Streets (CEOI17_oneway)C++20
0 / 100
3 ms7564 KiB
#include <iostream> #include <vector> #include <algorithm> #include <stack> #include <cassert> #include <map> #define ll long long using namespace std; const int NMAX = 1e5; const int LOGMAX = 18; struct Edge { int to, type, id; }; int n, m, q, t, components; pair<int, int> edges[NMAX + 1]; vector<Edge> g[NMAX + 1], tree[NMAX + 1]; vector<pair<int, int>> updates[NMAX + 1]; int dfs_time[NMAX + 1]; int low[NMAX + 1]; bool bridge[NMAX + 1]; int component[NMAX + 1]; Edge parent[NMAX + 1]; int depth[NMAX + 1]; int euler[2 * NMAX + 1], ind_e; int LOG[2 * NMAX + 1]; int pos_euler[NMAX + 1]; int rmq[LOGMAX + 1][2 * NMAX + 1]; int answer[NMAX + 1]; pair<int, int> node_with_depth[NMAX + 1]; map<pair<int, int>, int> mp; bool visited[NMAX + 1]; void DFS1(int node, int dad = 0) { dfs_time[node] = low[node] = ++t; for(auto [next_node, type, id] : g[node]) { if(!dfs_time[next_node]) { DFS1(next_node, node); low[node] = min(low[node], low[next_node]); if(low[next_node] > dfs_time[node] && mp.count(make_pair(node, next_node)) == 1) { bridge[id] = 1; } } else if(next_node != dad) { low[node] = min(low[node], dfs_time[next_node]); } } } void DFS2(int node) { component[node] = components; for(auto [next_node, type, id] : g[node]) { if(!component[next_node] && !bridge[id]) { DFS2(next_node); } } } void DFS3(int node, Edge dad_edge = {0, 0, 0}) { visited[node] = 1; parent[node] = dad_edge; depth[node] = depth[dad_edge.to] + 1; euler[++ind_e] = node; pos_euler[node] = ind_e; for(auto [next_node, type, id] : tree[node]) { if(next_node != dad_edge.to) { DFS3(next_node, {node, type, id}); euler[++ind_e] = node; } } } void Precompute() { for(int i = 2; i <= ind_e; i++) { LOG[i] = LOG[i >> 1] + 1; } for(int i = 1; i <= ind_e; i++) { rmq[0][i] = euler[i]; } for(int k = 1; (1 << k) <= ind_e; k++) { for(int i = 1; i + (1 << k) - 1 <= ind_e; i++) { int first_node = rmq[k - 1][i]; int second_node = rmq[k - 1][i + (1 << (k - 1))]; rmq[k][i] = (depth[first_node] < depth[second_node] ? first_node : second_node); } } } int GetLCA(int x, int y) { x = pos_euler[x]; y = pos_euler[y]; if(x > y) { swap(x, y); } int k = LOG[y - x + 1]; int first_node = rmq[k][x]; int second_node = rmq[k][y - (1 << k) + 1]; return (depth[first_node] < depth[second_node] ? first_node : second_node); } void UpdatePath(int x, int y, int type_need) { while(x != y && !answer[parent[x].to]) { assert(x > 0); Edge curent_edge = parent[x]; if(type_need == 1 && curent_edge.type == 0) { answer[curent_edge.id] = 2; } else if(type_need == 1 && curent_edge.type == 1) { answer[curent_edge.id] = 1; } else if(type_need == 0 && curent_edge.type == 0) { answer[curent_edge.id] = 1; } else { answer[curent_edge.id] = 2; } x = curent_edge.to; } } void Update(int lca, int x, int y) { UpdatePath(x, lca, 1); UpdatePath(y, lca, 0); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; edges[i] = {a, b}; mp[{a, b}]++; mp[{b, a}]++; g[a].push_back({b, 0, i}); g[b].push_back({a, 1, i}); } for(int i = 1; i <= n; i++) { if(!dfs_time[i]) { DFS1(i); } } for(int i = 1; i <= n; i++) { if(!component[i]) { components++; DFS2(i); } } for(int i = 1; i <= n; i++) { for(auto [j, type, id] : g[i]) { if(component[i] != component[j]) { tree[component[i]].push_back({component[j], type, id}); } } } for(int i = 1; i <= n; i++) { if(!visited[i]) { DFS3(i); } } Precompute(); cin >> q; while(q--) { int x, y; cin >> x >> y; x = component[x]; y = component[y]; updates[GetLCA(x, y)].push_back({x, y}); } for(int i = 1; i <= n; i++) { node_with_depth[i] = {depth[i], i}; } sort(node_with_depth + 1, node_with_depth + n + 1); for(int i = 1; i <= n; i++) { int node = node_with_depth[i].second; for(auto [x, y] : updates[node]) { Update(node, x, y); } } for(int i = 1; i <= m; i++) { if(answer[i] == 0) { cout << "B"; } else if(answer[i] == 1) { cout << "R"; } else { cout << "L"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...