oj.uz

Submission #255686

# Submission time Handle Problem Language Result Execution time Memory
255686 2020-08-01T14:29:51 Z Haunted_Cpp One-Way Streets (CEOI17_oneway) C++17
0 / 100
 5 ms 512 KB 
/**
 * author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

class Tarjan {
private:
  vector<int> low, id;
  int Time;
  const int L;
  set<pair<int, int>> bridge_count;
  void dfs(int node, int p, const vector<vector<int>> &g) {
    id[node] = low[node] = ++Time;
    for (auto to : g[node]) {
      if (to != p) {
        if(id[to] == -1) dfs(to, node, g);
        low[node] = min(low[node], low[to]);
        if (id[node] < low[to]) {
          bridge_count.insert({min(node, to), max(node, to)});
        }
      }
    }
  }
public:
  Tarjan(const vector<vector<int>> &g) : L((int)g.size()){
    low.clear();
    id.clear();
    bridge_count.clear();
    Time = 0;
    find_bridge(g);
  }
  void find_bridge(const vector<vector<int>> &g) {
    low = vector<int>(L, -1);
    id = vector<int>(L, -1);
    for (int i = 0; i < L; i++) {
      if (id[i] == -1) {
        dfs(i, -1, g);
      }
    }
  }
  bool is_bridge(int st, int et) {
    return bridge_count.find({min(st, et), max(st, et)}) != bridge_count.end();
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<pair<int, int>> edge(m);
  for (int i = 0; i < m; i++) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    edge[i] = {st, et};
    g[st].emplace_back(et);
    g[et].emplace_back(st);
  }
  Tarjan solve(g);
  string ans = string(m, 'B');
  for (int i = 0; i < m; i++) {
    if(solve.is_bridge(edge[i].first, edge[i].second) == true) {
      ans[i] = '-';
    }
  }
  set<pair<int, int>> dir;
  auto Bfs = [&](int source, int destination) {
    queue<int> q;
    q.push(source);
    vector<int> par(n, -1);
    vector<bool> vis(n, false);
    vis[source] = true;
    while(!q.empty()) {
      int node = q.front();
      q.pop();
      for (auto to : g[node]) {
        if (!vis[to]) {
          vis[to] = true;
          q.push(to);
          par[to] = node;
        }
      }
    }
    //~ debug("SOURCE: ", source + 1);
    int current_node = destination;
    while(current_node != -1) {
      int was = current_node;
      current_node = par[current_node];
      if (current_node == -1) break;
      //~ debug(current_node + 1, was + 1);
      dir.insert({current_node, was}); 
    }
  };
  int q;
  cin >> q;
  while(q--) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    Bfs(st, et);
  }
  for (int i = 0; i < m; i++) {
    if(ans[i] == '-') {
      if(dir.find({edge[i].first, edge[i].second}) != dir.end()) {
        ans[i] = 'R';
        assert(dir.find({edge[i].second, edge[i].first}) == dir.end());
        continue;
      } 
      if (dir.find({edge[i].second, edge[i].first}) != dir.end()) {
        ans[i] = 'L';
        assert(dir.find({edge[i].first, edge[i].second}) == dir.end());
        continue;
      }
      //~ debug(edge[i].second, edge[i].first);
      ans[i] = 'B';
    }
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Incorrect 3 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Incorrect 3 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Incorrect 3 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -