Submission #1091442

#TimeUsernameProblemLanguageResultExecution timeMemory
1091442raphaelpOne-Way Streets (CEOI17_oneway)C++14
30 / 100
3040 ms12360 KiB
#include <bits/stdc++.h> using namespace std; int dfs(int x, int p, int id, vector<vector<pair<int, int>>> &AR, int &buff, vector<int> &ordre, vector<int> &low, vector<int> &incycle, vector<int> &occ) { occ[x] = 1; if (low[x] != low.size()) { incycle.push_back(id); return low[x]; } ordre[x] = buff; low[x] = buff++; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i].second == id) continue; low[x] = min(low[x], dfs(AR[x][i].first, x, AR[x][i].second, AR, buff, ordre, low, incycle, occ)); } if (low[x] < ordre[x]) incycle.push_back(id); return low[x]; } int find(int x, vector<int> &p) { return (p[x] == x) ? x : p[x] = find(p[x], p); } int dfs2(int x, int par, int id, vector<int> &p, vector<vector<pair<int, int>>> &AR, vector<int> &cities, vector<char> &ans, vector<pair<int, int>> &aretes, vector<int> &occ) { occ[x] = 1; int cur = 0; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i].second == id) continue; if (find(AR[x][i].first, p) == x) continue; cur += dfs2(find(AR[x][i].first, p), x, AR[x][i].second, p, AR, cities, ans, aretes, occ); } cur += cities[x]; if (id < 0) return cur; if (cur == 0) ans[id] = 'B'; else { if (find(aretes[id].first, p) == x) { if (cur > 0) ans[id] = 'R'; else ans[id] = 'L'; } else { if (cur > 0) ans[id] = 'L'; else ans[id] = 'R'; } } return cur; } int main() { int N, M; cin >> N >> M; vector<vector<pair<int, int>>> AR(N); vector<pair<int, int>> aretes; for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--, b--; AR[a].push_back({b, i}); AR[b].push_back({a, i}); aretes.push_back({a, b}); } int buff = 0; vector<int> low(N, N), ordre(N); vector<int> incycle; vector<int> occ(N); for (int i = 0; i < N; i++) { if (occ[i]) continue; int temp = dfs(i, i, -1, AR, buff, ordre, low, incycle, occ); } vector<char> ans(M); vector<int> p(N), size(N, 1); for (int i = 0; i < N; i++) p[i] = i; for (int i = 0; i < incycle.size(); i++) { ans[incycle[i]] = 'B'; int x = find(aretes[incycle[i]].first, p), y = find(aretes[incycle[i]].second, p); if (x == y) continue; if (size[x] > size[y]) swap(x, y); p[x] = y; size[y] += size[x]; for (auto j : AR[x]) AR[y].push_back(j); } int P; cin >> P; vector<int> cities(N, 0); for (int i = 0; i < P; i++) { int a, b; cin >> a >> b; a--, b--; cities[find(a, p)]++; cities[find(b, p)]--; } occ.assign(N, 0); for (int i = 0; i < N; i++) { if (occ[i]) continue; int temp = dfs2(find(i, p), find(i, p), -1, p, AR, cities, ans, aretes, occ); } for (int i = 0; i < M; i++) cout << ans[i]; }

Compilation message (stderr)

oneway.cpp: In function 'int dfs(int, int, int, std::vector<std::vector<std::pair<int, int> > >&, int&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
oneway.cpp:6:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     if (low[x] != low.size())
oneway.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int dfs2(int, int, int, std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<char>&, std::vector<std::pair<int, int> >&, std::vector<int>&)':
oneway.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:86:13: warning: unused variable 'temp' [-Wunused-variable]
   86 |         int temp = dfs(i, i, -1, AR, buff, ordre, low, incycle, occ);
      |             ^~~~
oneway.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < incycle.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:121:13: warning: unused variable 'temp' [-Wunused-variable]
  121 |         int temp = dfs2(find(i, p), find(i, p), -1, p, AR, cities, ans, aretes, occ);
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...