Submission #902683

#TimeUsernameProblemLanguageResultExecution timeMemory
902683selmahbnOne-Way Streets (CEOI17_oneway)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; const int INF = numeric_limits<int>::max() / 2; vector<int> num, low, comp; stack<int> s; int dfs_count = 0; int comp_count = 0; vector<vector<int>> dir; vector<int> in; vector<int> out; void tarjan_dfs(int current, int parent, vector<vector<int>>& adj) { num[current] = low[current] = dfs_count; dfs_count++; s.push(current); for (int neigh : adj[current]) { if (num[neigh] == INF) { tarjan_dfs(neigh, current, adj); low[current] = min(low[current], low[neigh]); if (num[neigh] == low[neigh]) { while (s.top() != neigh) { int top = s.top(); s.pop(); comp[top] = comp_count; } s.pop(); comp[neigh] = comp_count; comp_count++; } } else if (neigh != parent) { low[current] = min(low[current], num[neigh]); } } } int dir_dfs(int current, vector<int>& visited, vector<vector<int>>& adj) { visited[current] = 1; int incoming = in[current] - out[current]; for (int neigh : adj[current]) { if (visited[neigh] == 0) { int d = dir_dfs(neigh, visited, adj); if (d < 0) { dir[current][neigh] = -1; dir[neigh][current] = 1; } else { dir[current][neigh] = 1; dir[neigh][current] = -1; } incoming += d; } } return incoming; } int main() { ios::sync_with_stdio(false); cin.tie(); cout.tie(); int n, m; cin >> n >> m; vector<vector<int>> adj(n); vector<pair<int, int>> streets; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); streets.push_back(make_pair(a, b)); } int p; cin >> p; vector<pair<int, int>> pairs; for (int i = 0; i < p; i++) { int a, b; cin >> a >> b; a--; b--; pairs.push_back(make_pair(a, b)); } num = vector<int>(n, INF); low = vector<int>(n); comp = vector<int>(n); for (int i = 0; i < n; i++) { if (num[i] == INF) { tarjan_dfs(i, i, adj); while (!s.empty()) { int top = s.top(); s.pop(); comp[top] = comp_count; } comp_count++; } } adj = vector<vector<int>>(comp_count); for (pair<int, int> s : streets) { if (comp[s.first] != comp[s.second]) { adj[comp[s.first]].push_back(comp[s.second]); adj[comp[s.second]].push_back(comp[s.first]); } } in = vector<int>(comp_count, 0); out = vector<int>(comp_count, 0); for (pair<int, int> p : pairs) { if (comp[p.first] != comp[p.second]) { out[comp[p.first]]++; in[comp[p.second]]++; } } vector<int> visited(comp_count, 0); dir = vector<vector<int>>(comp_count, vector<int>(comp_count, 0)); for (int i = 0; i < comp_count; i++) { if (visited[i] == 0) dir_dfs(i, visited, adj); } for (pair<int, int> s : streets) { if (comp[s.first] == comp[s.second] || dir[comp[s.first]][comp[s.second]] == 0) cout << "B"; else if (dir[comp[s.first]][comp[s.second]] == 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...