제출 #583368

#제출 시각아이디문제언어결과실행 시간메모리
583368600MihneaOne-Way Streets (CEOI17_oneway)C++17
100 / 100
234 ms57396 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 7;
const int K = 20;
vector<int> g[N], g2[N];
int n, m, q, sumEdge[N], dep[N], mindep[N], xx[N], yy[N], ff[N], ss[N], top, lg2[2 * N], par[N], sol[N], gp[N], gn[N];
pair<int, int> rmq[K][2 * N];
bool isBridge[N];
bool vis[N];
int color[N], currentColor;
map<pair<int, int>, int> coresp;

void dfs_build_bridges(int a, int parrent_edge_id = 0) {
  mindep[a] = dep[a];
  vector<int> downEdges;
  for (auto &i : g[a]) {
    int b = sumEdge[i] - a;
    if (dep[b] == -1) {
      dep[b] = 1 + dep[a];
      dfs_build_bridges(b, i);
      mindep[a] = min(mindep[a], mindep[b]);
      downEdges.push_back(i);
      continue;
    }
    if (i == parrent_edge_id) {
      continue;
    }
    mindep[a] = min(mindep[a], dep[b]);
  }
  for (auto &i : downEdges) {
    int b = sumEdge[i] - a;
    if (dep[a] < mindep[b]) {
      isBridge[i] = 1;
    }
  }
}

void dfsColor(int a) {
  color[a] = currentColor;
  for (auto &i : g[a]) {
    int b = sumEdge[i] - a;
    if (isBridge[i]) {
      if (color[b]) {
        coresp[{color[xx[i]], color[yy[i]]}] = i;
        g2[color[a]].push_back(color[b]);
        g2[color[b]].push_back(color[a]);
      }
      continue;
    }
    if (color[b] == 0) {
      dfsColor(b);
    }
  }
}

void dfs(int a) {
  vis[a] = 1;
  rmq[0][++top] = {dep[a], a};
  ff[a] = ss[a] = top;
  for (auto &b : g[a]) {
    if (vis[b] == 0) {
      par[b] = a;
      dep[b] = 1 + dep[a];
      dfs(b);
      rmq[0][++top] = {dep[a], a};
      ss[a] = top;
    }
  }
}

int getLca(int a, int b) {
  if (ff[a] > ss[b]) {
    swap(a, b);
  }
  assert(ff[a] <= ss[b]);
  a = ff[a];
  b = ss[b];
  int k = lg2[b - a + 1];
  return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}

void dfstot(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfstot(b, a);
    }
  }
  gp[p] = max(gp[p], gp[a] - 1);
  gn[p] = max(gn[p], gn[a] - 1);
}

int dir[N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    dep[i] = -1;
  }
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    xx[i] = a;
    yy[i] = b;
    sumEdge[i] = a + b;
    g[a].push_back(i);
    g[b].push_back(i);
  }

  for (int i = 1; i <= n; i++) {
    if (dep[i] == -1) {
      dep[i] = 0;
      dfs_build_bridges(i);
    }
  }


  for (int i = 1; i <= n; i++) {
    if (color[i] == 0) {
      currentColor++;
      dfsColor(i);
    }
  }

  for (int i = 1; i <= currentColor; i++) {
    g[i] = g2[i];
  }

  for (int i = 1; i <= currentColor; i++) {
    vis[i] = 0;
    dep[i] = 0;
  }
  vector<int> rts;
  for (int i = 1; i <= currentColor; i++) {
    if (vis[i] == 0) {
      dep[i] = 0;
      rts.push_back(i);
      dfs(i);
    }
  }
  for (int i = 2; i <= top; i++) {
    lg2[i] = 1 + lg2[i / 2];
  }
  for (int k = 1; (1 << k) <= top; k++) {
    for (int i = 1; i + (1 << k) - 1 <= top; i++) {
      rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
    }
  }

  cin >> q;

  for (int i = 1; i <= q; i++) {
    int a, b;
    cin >> a >> b;
    a = color[a];
    b = color[b];
    int c = getLca(a, b);
    gn[a] = max(gn[a], dep[a] - dep[c]);
    gp[b] = max(gp[b], dep[b] - dep[c]);
  }

  for (auto &i : rts) {
    dfstot(i);
  }
  for (int i = 1; i <= currentColor; i++) {
    assert((gp[i] == 0) || (gn[i] == 0));
    if (gp[i]) {
      dir[i] = +1;
    }
    if (gn[i]) {
      dir[i] = -1;
    }
    if (dir[i] != 0) {

      assert(coresp.count({i, par[i]}) || coresp.count({par[i], i}));
      if (coresp.count({i, par[i]})) {
        sol[coresp[{i, par[i]}]] = dir[i];
      } else {
        sol[coresp[{par[i], i}]] = -dir[i];
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    if (sol[i] == 0) {
      cout << "B";
    } else {
      if (sol[i] == -1) {
        cout << "R";
      } else {
        assert(sol[i] == +1);
        cout << "L";
      }
    }
  }
  cout << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...