Submission #570731

#	Time	Username	Problem	Language	Result	Execution time	Memory
570731		Shin	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	11 ms	10068 KiB

oneway

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int LOG = 20;
const int N = 1e5 + 7;

vector<pair<int, int>> adj[N];
vector<pair<int, int>> g[N];

int n, m;
int num_comps;
int comps[N];
int num[N];
int low[N];
int timer;
int depth[N];
int par[N][LOG + 1];

bool R[N], L[N];
int sum_R[N], sum_L[N];

stack<int> st;
pair<int, int> e[N];

void dfs1(int u, int p) {
  num[u] = low[u] = ++ timer;
  st.push(u);
  for (pair<int, int> v: adj[u]) if (v.se != p) {
    if (num[v.fi]) {
      minimize(low[u], num[v.fi]);
    } else {
      dfs1(v.fi, v.se);
      minimize(low[u], low[v.fi]);
    }
  } 
  if (low[u] == num[u]) {
    int v;
    num_comps ++;
    do {
      v = st.top();
      st.pop();
      low[v] = num[v] = N;
      comps[v] = num_comps;
    } while (u != v);
  }
}

void dfs2(int u, int p) {
  par[u][0] = p;
  for (int i = 1; i <= LOG; i ++) {
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  for (pair<int, int> v: g[u]) if (v.fi != p) {
    depth[v.fi] = depth[u] + 1;
    dfs2(v.fi, u);
  }
}

int lca(int u, int v) {
  if (depth[v] > depth[u]) {
    swap(u, v);
  }
  int dist = depth[u] - depth[v];
  for (int i = LOG; i >= 0; i --) if ((dist >> i) & 1) {
    u = par[u][i];
  }
  if (u == v) {
    return u;
  }
  for (int i = LOG; i >= 0; i --) if (par[u][i] != par[v][i]) {
    u = par[u][i];
    v = par[v][i];
  }
  return par[u][0];
}

void build_tree() {
  for (int u = 1; u <= n; u ++) {
    for (pair<int, int> v: adj[u]) {
      if (comps[v.fi] != comps[u]) {
        g[comps[u]].emplace_back(comps[v.fi], v.se);
      }
    }
  }
  dfs2(1, 1);
}

void dfs3(int u, int p) {
  for (pair<int, int> v: g[u]) if (v.fi != p) {
    dfs3(v.fi, u);
    int f, t; tie(f, t) = e[v.se];
    bool dir = (u == comps[f] && v.fi == comps[t]);
    // if (u == 1) {
    //   cout << comps[f] << " " << comps[t] << '\n';
    // }
    if (sum_R[v.fi]) {
      (dir ? R[v.se] = true : L[v.se] = true);
    }
    if (sum_L[v.fi]) {
      (dir ? L[v.se] = true : R[v.se] = true);
    }
    sum_L[u] += sum_L[v.fi];
    sum_R[u] += sum_R[v.fi];
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i ++) {
    int u, v; cin >> u >> v;
    e[i] = mp(u, v);
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
  } 
  for (int i = 1; i <= n; i ++) {
    if (!num[i]) {
      assert(i == 1);
      dfs1(i, 0);
    }
  }
  build_tree();
  // for (int i = 1; i <= n; i ++) {
  //   cerr << i << " -> " << comps[i] << '\n';
  // }
  int q; cin >> q; 
  for (int i = 1; i <= q; i ++) {
    int u, v; cin >> u >> v;
    u = comps[u];
    v = comps[v];
    int w = lca(u, v);
    // u -> w -> v
    sum_L[u] ++;
    sum_L[w] --;
    sum_R[v] ++;
    sum_R[w] --;
    // cerr << w << '\n';
  }
  dfs3(1, -1);
  for (int i = 1; i <= m; i ++) {
    // cerr << L[i] << " " << R[i] << '\n';
    if (L[i] + R[i] != 1) {
      cout << "B";
    } else {
      cout << (R[i] ? "R" : "L");
    }
    // cerr << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40