oj.uz

Submission #255688

# Submission time Handle Problem Language Result Execution time Memory
255688 2020-08-01T14:37:08 Z Haunted_Cpp One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 31468 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;
  map<pair<int, int>, int> cnt;
  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;
    ++cnt[{st, et}];
    ++cnt[{et, st}];
    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(cnt[edge[i]] == 1 && solve.is_bridge(edge[i].first, edge[i].second) == true) {
      debug(edge[i]);
      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;
        }
      }
    }
    int current_node = destination;
    while(current_node != -1) {
      int was = current_node;
      current_node = par[current_node];
      if (current_node == -1) break;
      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 (edge[i].first == edge[i].second) {
      ans[i] = 'B';
      continue;
    }
    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;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:86:21: warning: statement has no effect [-Wunused-value]
       debug(edge[i]);
                     ^

Subtask #1
30.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 2 ms 512 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct

Subtask #2
30.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 2 ms 512 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 483 ms 18680 KB Output is correct
12 Correct 485 ms 20088 KB Output is correct
13 Correct 653 ms 22064 KB Output is correct
14 Correct 946 ms 24380 KB Output is correct
15 Correct 1106 ms 25008 KB Output is correct
16 Correct 456 ms 26604 KB Output is correct
17 Correct 1999 ms 30084 KB Output is correct
18 Correct 1523 ms 27016 KB Output is correct
19 Correct 1651 ms 31468 KB Output is correct
20 Correct 679 ms 20588 KB Output is correct
21 Correct 540 ms 19588 KB Output is correct

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 2 ms 512 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 483 ms 18680 KB Output is correct
12 Correct 485 ms 20088 KB Output is correct
13 Correct 653 ms 22064 KB Output is correct
14 Correct 946 ms 24380 KB Output is correct
15 Correct 1106 ms 25008 KB Output is correct
16 Correct 456 ms 26604 KB Output is correct
17 Correct 1999 ms 30084 KB Output is correct
18 Correct 1523 ms 27016 KB Output is correct
19 Correct 1651 ms 31468 KB Output is correct
20 Correct 679 ms 20588 KB Output is correct
21 Correct 540 ms 19588 KB Output is correct
22 Execution timed out 3070 ms 30796 KB Time limit exceeded
23 Halted 0 ms 0 KB -