Submission #981058

#	Time	Username	Problem	Language	Result	Execution time	Memory
981058		badont	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	348 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

// clang-format off
template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable<    T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>    : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) {  return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) {  cout << "[";  for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", ";  } return cout << "]";}

#ifdef LOCAL
  void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
  #define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
  #define debug(...) "zzz"
#endif
// clang-format on

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

void solve() {
  // open
  int n, m, p;
  cin >> n >> m;

  vector e(n, vector<pii>());
  vector<pii> edges(m);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    e[a].pb({b, i});
    e[b].pb({a, i});
    // debug(a, b);
    edges[i] = {a, b};
  }

  cin >> p;

  vector r(n, vector<int>());
  vector<pii> rq(p);
  for (int i = 0; i < p; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    // x going to y
    r[x].pb(i);
    r[y].pb(i);
    rq[i] = {x, y};
  }

  vector<bool> v(n, false);
  vector<int> depth(n, 0);
  vector<int> parent(n, -1);
  vector<int> parent_edge(n, -1);
  vector<set<int>> reqs(n);
  vector<int> tin(n, -1);
  vector<int> tout(n, -1);

  vector<int> ans(m, 0);
  for (int i = 0; i < n; i++) {
    if (v[i])
      continue;
    // returns num back edges
    int cc = 0;
    auto dfs = [&](auto &dfs, int g, int p, int d, int pi) -> int {
      v[g] = true;
      depth[g] = d;
      parent[g] = p;
      parent_edge[g] = pi;
      tin[g] = cc++;

      vector<pii> back_edges, rev_back_edges;
      int num_add = 0, num_sub = 0;
      int total_be = 0, total_up = 0, total_down = 0;
      for (const auto &[u, idx] : e[g]) {
        // debug(u, idx);
        if (v[u]) {
          if (idx != parent_edge[g] and depth[u] < depth[g]) {
            // back edge
            num_add++;
          } else if (idx != parent_edge[u] and depth[u] > depth[g]) {
            num_sub++;
          }
        } else {
          int num_back_edges = dfs(dfs, u, g, d + 1, idx);
          total_be += num_back_edges;

          if (num_back_edges == 0) {
            if (!reqs[u].empty()) {
              int idx_beg = *reqs[u].begin();
              const auto [f, l] = rq[idx_beg];
              const auto [fu, lu] = edges[idx_beg];

              if (tin[u] <= tin[f] and tout[u] >= tout[f]) {
                // go out
                ans[idx] = (u == fu ? 1 : 2);
              } else {
                ans[idx] = (u == fu ? 2 : 1);
              }
            }
          }

          if (reqs[u].size() > reqs[g].size()) {
            swap(reqs[u], reqs[g]);
          }
          for (auto x : reqs[u]) {
            if (reqs[g].count(x)) {
              reqs[g].erase(x);
            } else {
              reqs[g].insert(x);
            }
          }
          reqs[u].clear();
        }
      }

      total_be += num_add - num_sub;
      for (auto u : r[g]) {
        if (reqs[g].count(u)) {
          reqs[g].erase(u);
        } else {
          reqs[g].insert(u);
        }
      }

      tout[g] = cc++;
      return total_be;
    };

    dfs(dfs, i, -1, 0, -1);
  }

  for (int i = 0; i < m; i++) {
    if (ans[i] == 0) {
      cout << "B";
    } else if (ans[i] == 1) {
      cout << "L";
    } else {
      cout << "R";
    }
  }
  cout << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(false);

  ll T = 1;
  // cin >> T;
  for (int t = 0; t < T; t++)
    solve();

  cout.flush();
  return 0;
}

Compilation message (stderr)

oneway.cpp: In instantiation of 'solve()::<lambda(auto:23&, int, int, int, int)> [with auto:23 = solve()::<lambda(auto:23&, int, int, int, int)>]':
oneway.cpp:135:27:   required from here
oneway.cpp:79:25: warning: unused variable 'total_up' [-Wunused-variable]
   79 |       int total_be = 0, total_up = 0, total_down = 0;
      |                         ^~~~~~~~
oneway.cpp:79:39: warning: unused variable 'total_down' [-Wunused-variable]
   79 |       int total_be = 0, total_up = 0, total_down = 0;
      |                                       ^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40