Submission #255806

#	Time	Username	Problem	Language	Result	Execution time	Memory
255806		Haunted_Cpp	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	570 ms	65916 KiB

oneway

/**
 * 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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40