oj.uz

Submission #679835

# Submission time Handle Problem Language Result Execution time Memory
679835 2023-01-09T11:52:58 Z peijar One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3 ms 2772 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e5;

struct UnionFind {
  vector<int> id;

  UnionFind() {}
  UnionFind(int N) { id.assign(N, -1); }

  int find(int u) {
    if (id[u] < 0)
      return u;
    return id[u] = find(id[u]);
  }

  bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return false;
    if (id[u] > id[v])
      swap(u, v);
    id[u] += id[v];
    id[v] = u;
    return true;
  }
};

vector<pair<int, int>> adj[MAXN];
vector<pair<int, int>> edges;
vector<int> num, st;
int Time;
vector<int> bridges;
bool isBridge[MAXN];

int dfs(int at, int par) {
  int me = num[at] = ++Time, e, y, top = me;

  for (auto pa : adj[at])
    if (pa.second != par) {
      tie(y, e) = pa;
      if (num[y])
        top = min(top, num[y]);
      else {
        int up = dfs(y, e);
        top = min(top, up);
        if (up == me) {
        } else if (up < me) {
        } else {
          bridges.push_back(e);
          isBridge[e] = true;
        }
      }
    }
  return top;
}

void bicomps() {
  num.assign(edges.size(), 0);
  for (int i = 0; i < (int)edges.size(); ++i)
    if (!num[i])
      dfs(i, -1);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbAretes, nbRequetes;
  cin >> nbSommet >> nbAretes;
  edges.resize(nbAretes);
  for (int i = 0; i < nbAretes; ++i) {
    auto &[u, v] = edges[i];
    cin >> u >> v;
    --u, --v;
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
  }

  cin >> nbRequetes;
  vector<pair<int, int>> queries(nbRequetes);
  for (auto &[u, v] : queries) {
    cin >> u >> v;
    --u, --v;
  }

  bicomps();

  UnionFind dsu(nbSommet);
  for (int i = 0; i < nbAretes; ++i)
    if (!isBridge[i])
      dsu.merge(edges[i].first, edges[i].second);
  vector<int> roots;
  for (int u = 0; u < nbSommet; ++u)
    if (dsu.find(u) == u)
      roots.push_back(u);

  auto getId = [&](int u) {
    return lower_bound(roots.begin(), roots.end(), dsu.find(u)) - roots.begin();
  };
  for (int u = 0; u < nbSommet; ++u)
    adj[u].clear();
  for (int iArete = 0; iArete < nbAretes; ++iArete) {
    if (isBridge[iArete]) {
      auto [u, v] = edges[iArete];
      u = getId(u);
      v = getId(v);
      if (u == v)
        continue;
      adj[u].emplace_back(v, iArete);
      adj[v].emplace_back(u, iArete);
    }
  }
  int nbRoots = roots.size();
  vector<int> cntDeb(nbRoots), cntFin(nbRoots);
  for (auto [u, v] : queries) {
    u = getId(u);
    v = getId(v);
    if (u == v)
      continue;
    cntDeb[u]++;
    cntFin[v]++;
  }

  vector<int> side(nbAretes);
  vector<bool> seen(nbRoots);

  auto dfsBridge = [&](auto rec, int u, int p) -> void {
    seen[u] = true;
    for (auto [v, id] : adj[u])
      if (v != p) {
        rec(rec, v, u);
        cntDeb[u] += cntDeb[v];
        cntFin[u] += cntFin[v];
        if (cntDeb[v] > cntFin[v]) {
          side[id] = getId(edges[id].first) == u ? -1 : 1;
        }
        if (cntFin[v] > cntDeb[v])
          side[id] = getId(edges[id].first) == u ? 1 : -1;
      }
  };

  for (int u = 0; u < nbRoots; ++u)
    if (!seen[u])
      dfsBridge(dfsBridge, u, u);
  for (int x : side) {
    if (x == 0)
      cout << 'B';
    else if (x == -1)
      cout << 'L';
    else
      cout << 'R';
  }
  cout << endl;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -