제출 #583364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583364		600Mihnea	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3057 ms	54800 KiB

oneway

#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];
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;
}

int dir[N];

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

///  freopen ("input.txt", "r", stdin);
///  freopen ("output.txt", "w", stdout);
///

  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);
  }
  /// build the Tree

  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;
  }
  for (int i = 1; i <= currentColor; i++) {
    if (vis[i] == 0) {
      dep[i] = 0;
      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))]);
    }
  }
 /* exit(0);
  for (int i = 1; i <= n; i++) {
    cout << i << " : " << color[i] << "\n";
  }

  cout << "----------------\n";

  for (int i = 1; i <= currentColor; i++) {
    for (auto &j : g[i]) {
      cout << "Edge = " << i << " " << j << "\n";
    }
  }

  return 0;

  for (int i = 1; i <= m; i++) {
    if (isBridge[i]) {
      cout << "bridge : " << xx[i] << " " << yy[i] << "\n";
    }
  }*/




  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);
    //cout << a << " " << b << " -> " << c << "\n";
    while (a != c) {
      assert(a > 0);
      assert(dir[a] == -1 || dir[a] == 0);
      dir[a] = -1;
      a = par[a];
    }
    while (b != c) {
      assert(b > 0);
      assert(dir[b] == +1 || dir[b] == 0);
      dir[b] = +1;
      b = par[b];
    }
  }

  for (int i = 1; i <= currentColor; i++) {
    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";
}

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