oj.uz

Submission #255806

# Submission time Handle Problem Language Result Execution time Memory
255806 2020-08-01T21:54:32 Z Haunted_Cpp One-Way Streets (CEOI17_oneway) C++17
100 / 100
 570 ms 65916 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

const int MAX_N = 1e5 + 5;
const int MAX_K = 20 + 5;

map<int, int> chk_double[MAX_N];

vector<vector<int>> g(MAX_N);
vector<pair<int, int>> edge_list(MAX_N);

// Bridge Finding Procedure
vector<int> low(MAX_N), disc(MAX_N);
int Time = 0;
set<int> bridge[MAX_N];

void tarjan(int node, int p) {
  low[node] = disc[node] = ++Time;
  for (auto to : g[node]) {
    if (to != p) {
      if(!disc[to]) tarjan(to, node);
      low[node] = min(low[node], low[to]);
      if (chk_double[node][to] == 1 && disc[node] < low[to]) {
        bridge[min(node, to)].insert(max(node, to));
      }
    }
  }
} 
     
bool is_bridge(int st, int et) {
  if (st > et) swap(st, et);
  return bridge[st].find(et) != bridge[st].end();
}

// Compress Procedure
vector<int> cor(MAX_N);
vector<vector<tuple<int, int, int>>> dag(MAX_N);

void paint(int node, int p) {
  cor[node] = Time;
  for (auto to : g[node]) {
    if (to == p) continue;
    if (is_bridge(node, to)) continue;
    if (cor[to]) continue;
    cor[to] = Time;
    paint(to, node);
  }
}

// LCA
int dp[MAX_N][MAX_K];
vector<int> H(MAX_N, -1);

void dfs(int node, int p) {
  if (H[node] == -1) H[node] = 0;
  dp[node][0] = p;
  for (auto nxt : dag[node]) {
    const int to = get<0>(nxt);
    if (to == p) continue;
    H[to] = H[node] + 1;
    dfs(to, node);
  }
}

int lca(int u, int v) {
  if (H[u] < H[v]) swap(u, v);
  int d = H[u] - H[v];
  for (int i = 0; i < MAX_K; i++) {
    if ((d >> i) & 1) {
      u = dp[u][i];
    }
  }
  if (u == v) return u;
  for (int i = MAX_K - 1; ~i; i--) {
    if (dp[u][i] != dp[v][i]) {
      u = dp[u][i];
      v = dp[v][i];
    }
  }
  return dp[u][0];
}

// Calculate answer
bool vis[MAX_N];
vector<int> L(MAX_N), R(MAX_N);

set<pair<int, int>> dir;

int solve_l(int node, int p) {
  vis[node] = true;
  for (auto nxt : dag[node]) {
    const int to = get<0>(nxt);
    if (to == p) continue;
    L[node] += solve_l(to, node);
    if(L[to] > 0) {
      const int st = get<1>(nxt);
      const int et = get<2>(nxt);
      dir.insert({et, st});
    }
  }
  return L[node];
}

int solve_r(int node, int p) {
  vis[node] = true;
  for (auto nxt : dag[node]) {
    const int to = get<0>(nxt);
    if (to == p) continue;
    R[node] += solve_r(to, node);
    if (node == 3) debug(to, R[to]);
    if(R[to] > 0) {
      const int st = get<1>(nxt);
      const int et = get<2>(nxt);
      dir.insert({st, et});
      //~ debug("DOWN: ", st, et);
    }
  }
  return R[node];
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    edge_list[i] = {st, et};
    ++chk_double[st][et];
    ++chk_double[et][st];
    g[st].emplace_back(et);
    g[et].emplace_back(st);
  }
  // Find all bridges
  for (int i = 0; i < n; i++) {
    if (!disc[i]) {
      tarjan(i, -1);
    }
  }
  // Mark components and compress
  Time = 0;
  for (int i = 0; i < n; i++) {
    if (!cor[i]) {
      ++Time;
      paint(i, -1);
    }
  }
  set<pair<int, int>> stk;
  for (int st = 0; st < n; st++) {
    for (auto et : g[st]) {
      if (stk.find({min(cor[st], cor[et]), max(cor[st], cor[et])}) != stk.end()) {
        continue;
      }
      if (cor[st] != cor[et]) {
        stk.insert({min(cor[st], cor[et]), max(cor[st], cor[et])});
        dag[cor[st]].emplace_back(make_tuple(cor[et], st, et));
        dag[cor[et]].emplace_back(make_tuple(cor[st], et, st));
      }
    }
  }
  // LCA and start routines
  memset(dp, -1, sizeof(dp));
  for (int i = 1; i <= Time; i++) {
    if (H[i] == -1) {
      debug(i);
      dfs(i, -1);
    }
  }
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 1; i <= Time; i++) {
      if (~dp[i][j - 1]) {
        dp[i][j] = dp[dp[i][j - 1]][j - 1];
      }
    }
  }
  int q;
  cin >> q;
  while(q--) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    st = cor[st];
    et = cor[et];
    
    // UP
    --L[lca(st, et)];
    ++L[st];
    
    // DOWN
    --R[lca(st, et)];
    ++R[et];
    
    //~ debug(st, et, lca(st, et));
  }
  memset(vis, false, sizeof(vis));
  for (int i = 1; i <= Time; i++) {
    if (!vis[i]) {
      solve_l(i, -1);
      solve_r(i, -1);
    }
  }
  for (int i = 0; i < m; i++) {
    const int st = edge_list[i].first;
    const int et = edge_list[i].second;
    if (dir.find({st, et}) != dir.end()) {
      cout << 'R';
      continue;
    }
    if (dir.find({et, st}) != dir.end()) {
      cout << 'L';
      continue;
    }
    cout << 'B';
  }
  cout << '\n';
  return 0;
}

Compilation message

oneway.cpp: In function 'int solve_r(int, int)':
oneway.cpp:130:36: warning: statement has no effect [-Wunused-value]
     if (node == 3) debug(to, R[to]);
                                    ^
oneway.cpp: In function 'int main()':
oneway.cpp:187:15: warning: statement has no effect [-Wunused-value]
       debug(i);
               ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27520 KB Output is correct
2 Correct 17 ms 27440 KB Output is correct
3 Correct 17 ms 27648 KB Output is correct
4 Correct 23 ms 27776 KB Output is correct
5 Correct 20 ms 27776 KB Output is correct
6 Correct 17 ms 27520 KB Output is correct
7 Correct 20 ms 27776 KB Output is correct
8 Correct 24 ms 27776 KB Output is correct
9 Correct 20 ms 27648 KB Output is correct
10 Correct 17 ms 27520 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27520 KB Output is correct
2 Correct 17 ms 27440 KB Output is correct
3 Correct 17 ms 27648 KB Output is correct
4 Correct 23 ms 27776 KB Output is correct
5 Correct 20 ms 27776 KB Output is correct
6 Correct 17 ms 27520 KB Output is correct
7 Correct 20 ms 27776 KB Output is correct
8 Correct 24 ms 27776 KB Output is correct
9 Correct 20 ms 27648 KB Output is correct
10 Correct 17 ms 27520 KB Output is correct
11 Correct 192 ms 41080 KB Output is correct
12 Correct 215 ms 42108 KB Output is correct
13 Correct 211 ms 43384 KB Output is correct
14 Correct 244 ms 46200 KB Output is correct
15 Correct 293 ms 47240 KB Output is correct
16 Correct 366 ms 55032 KB Output is correct
17 Correct 359 ms 58616 KB Output is correct
18 Correct 373 ms 55032 KB Output is correct
19 Correct 348 ms 59896 KB Output is correct
20 Correct 189 ms 41592 KB Output is correct
21 Correct 143 ms 41012 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27520 KB Output is correct
2 Correct 17 ms 27440 KB Output is correct
3 Correct 17 ms 27648 KB Output is correct
4 Correct 23 ms 27776 KB Output is correct
5 Correct 20 ms 27776 KB Output is correct
6 Correct 17 ms 27520 KB Output is correct
7 Correct 20 ms 27776 KB Output is correct
8 Correct 24 ms 27776 KB Output is correct
9 Correct 20 ms 27648 KB Output is correct
10 Correct 17 ms 27520 KB Output is correct
11 Correct 192 ms 41080 KB Output is correct
12 Correct 215 ms 42108 KB Output is correct
13 Correct 211 ms 43384 KB Output is correct
14 Correct 244 ms 46200 KB Output is correct
15 Correct 293 ms 47240 KB Output is correct
16 Correct 366 ms 55032 KB Output is correct
17 Correct 359 ms 58616 KB Output is correct
18 Correct 373 ms 55032 KB Output is correct
19 Correct 348 ms 59896 KB Output is correct
20 Correct 189 ms 41592 KB Output is correct
21 Correct 143 ms 41012 KB Output is correct
22 Correct 529 ms 62256 KB Output is correct
23 Correct 477 ms 60408 KB Output is correct
24 Correct 570 ms 60668 KB Output is correct
25 Correct 491 ms 65916 KB Output is correct
26 Correct 555 ms 61816 KB Output is correct
27 Correct 537 ms 60408 KB Output is correct
28 Correct 81 ms 30328 KB Output is correct
29 Correct 170 ms 42232 KB Output is correct
30 Correct 185 ms 42360 KB Output is correct
31 Correct 176 ms 42744 KB Output is correct
32 Correct 264 ms 47736 KB Output is correct