oj.uz

답안 #981065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981065 2024-05-12T18:49:16 Z badont One-Way Streets (CEOI17_oneway) C++17
100 / 100
 238 ms 41120 KB 
#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);
  constexpr int INF = 1e8;
  vector<int> tin(n, -INF);
  vector<int> tout(n, INF);

  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) {
            // debug("bridge:", idx);
            if (!reqs[u].empty()) {
              int idx_beg = *reqs[u].begin();
              const auto [f, l] = rq[idx_beg];
              const auto [fu, lu] = edges[idx];
              debug(f, l, fu, lu);

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

          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

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:139:27:   required from here
oneway.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
oneway.cpp:100:15: note: in expansion of macro 'debug'
  100 |               debug(f, l, fu, lu);
      |               ^~~~~
oneway.cpp:80:25: warning: unused variable 'total_up' [-Wunused-variable]
   80 |       int total_be = 0, total_up = 0, total_down = 0;
      |                         ^~~~~~~~
oneway.cpp:80:39: warning: unused variable 'total_down' [-Wunused-variable]
   80 |       int total_be = 0, total_up = 0, total_down = 0;
      |                                       ^~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 27 ms 10588 KB Output is correct
12 Correct 35 ms 13732 KB Output is correct
13 Correct 38 ms 17748 KB Output is correct
14 Correct 47 ms 21332 KB Output is correct
15 Correct 67 ms 22380 KB Output is correct
16 Correct 45 ms 18000 KB Output is correct
17 Correct 52 ms 22356 KB Output is correct
18 Correct 45 ms 18004 KB Output is correct
19 Correct 48 ms 25168 KB Output is correct
20 Correct 33 ms 14684 KB Output is correct
21 Correct 31 ms 13908 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 27 ms 10588 KB Output is correct
12 Correct 35 ms 13732 KB Output is correct
13 Correct 38 ms 17748 KB Output is correct
14 Correct 47 ms 21332 KB Output is correct
15 Correct 67 ms 22380 KB Output is correct
16 Correct 45 ms 18000 KB Output is correct
17 Correct 52 ms 22356 KB Output is correct
18 Correct 45 ms 18004 KB Output is correct
19 Correct 48 ms 25168 KB Output is correct
20 Correct 33 ms 14684 KB Output is correct
21 Correct 31 ms 13908 KB Output is correct
22 Correct 182 ms 35416 KB Output is correct
23 Correct 216 ms 30812 KB Output is correct
24 Correct 238 ms 29456 KB Output is correct
25 Correct 197 ms 41120 KB Output is correct
26 Correct 171 ms 33044 KB Output is correct
27 Correct 194 ms 30272 KB Output is correct
28 Correct 62 ms 8612 KB Output is correct
29 Correct 151 ms 24680 KB Output is correct
30 Correct 146 ms 23732 KB Output is correct
31 Correct 139 ms 22780 KB Output is correct
32 Correct 138 ms 29428 KB Output is correct