oj.uz

답안 #438495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438495 2021-06-28T06:03:04 Z xiaowuc1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 387 ms 39240 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(0) cerr
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

// THESE MUST BE THE UNION FIND VERTICES
int anc[100005][17];
int depth[100005];

int getlca(int a, int b) {
  if(depth[a] < depth[b]) swap(a, b);
  for(int d = 16; d >= 0; d--) if(depth[a] - depth[b] >= (1<<d)) a = anc[a][d];
  assert(depth[a] == depth[b]);
  for(int d = 16; d >= 0; d--) if(anc[a][d] != anc[b][d]) a = anc[a][d], b = anc[b][d];
  if(a != b) return anc[a][0];
  return a;
}

set<pii> forced;
int downv[100005]; // x->z->y, downv[y]--, downv[z]++
int upv[100005]; // x->z->y, upv[y]--, upv[x]++
vector<pii> edges[100005];
bool seen[100005];

set<int> treeedges[100005];
pii dfsforforce(int curr, int par) {
  seen[curr] = true;
  pii ret = {downv[curr], upv[curr]};
  for(auto out: treeedges[curr]) {
    if(seen[out]) continue;
    pii cand = dfsforforce(out, curr);
    ret.f += cand.f;
    ret.s += cand.s;
  }
  assert(ret.f <= 0 || ret.s <= 0);
  if(ret.f < 0) forced.emplace(par, curr);
  if(ret.s < 0) forced.emplace(curr, par);
  return ret;
}

int par[100005];
int find(int x) {
  return par[x] == x ? x : (par[x] = find(par[x]));
}
bool merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return false;
  par[x] = y;
  return true;
}

void dfsforlca(int curr) {
  seen[curr] = true;
  for(auto out: treeedges[curr]) {
    if(seen[out]) continue;
    depth[out] = depth[curr] + 1;
    anc[out][0] = curr;
    dfsforlca(out);
  }
}

int lhsedge[100005];
int rhsedge[100005];
int instack[100005];

int cyclecompensate[100005];
int dfsforcycle(int curr, int edgeIndex, vector<int>& v) {
  instack[curr] = sz(v);
  v.pb(curr);
  seen[curr] = true;
  int ret = 0;
  for(auto out: edges[curr]) {
    if(out.s == edgeIndex) continue;
    if(out.f == curr) continue;
    if(instack[out.f] >= 0) {
      derr << "cycle found between " << curr << " and " << out.f << endl;
      for(auto out: v) derr << out << " "; derr << endl;
      ret++;
      cyclecompensate[instack[out.f]]--;
      continue;
    }
    if(!seen[out.f]) {
      ret += dfsforcycle(out.f, out.s, v);
    }
  }
  ret += cyclecompensate[sz(v)-1];
  cyclecompensate[sz(v)-1] = 0;
  assert(instack[curr] == sz(v) - 1);
  instack[curr] = -1;
  assert(v.back() == curr);
  v.pop_back();
  if(ret > 0) {
    assert(sz(v));
    derr << "try to merge " << curr << " and " << v.back() << endl;
    merge(curr, v.back());
  }
  return ret;
}

void solve() {
  memset(instack, -1, sizeof(instack));
  int n, m;
  cin >> n >> m;
  iota(par, par+n+1, 0);
  for(int i = 0; i < m; i++) {
    cin >> lhsedge[i] >> rhsedge[i];
    edges[lhsedge[i]].eb(rhsedge[i], i);
    edges[rhsedge[i]].eb(lhsedge[i], i);
  }
  for(int i = 1; i <= n; i++) {
    if(!seen[i]) {
      vector<int> v;
      assert(dfsforcycle(i, -1, v) == 0);
    }
  }
  for(int i = 0; i < m; i++) {
    lhsedge[i] = find(lhsedge[i]);
    rhsedge[i] = find(rhsedge[i]);
  }
  for(int i = 0; i < m; i++) {
    if(lhsedge[i] == rhsedge[i]) continue;
    treeedges[lhsedge[i]].insert(rhsedge[i]);
    treeedges[rhsedge[i]].insert(lhsedge[i]);
  }
  memset(seen, 0, sizeof(seen));
  for(int i = 1; i <= n; i++) {
    if(!seen[i]) {
      dfsforlca(i);
    }
  }
  for(int d = 1; d < 17; d++) for(int i = 1; i <= n; i++) anc[i][d] = anc[anc[i][d-1]][d-1];
  int q;
  cin >> q;
  while(q--) {
    int x, y;
    cin >> x >> y;
    if(find(x) == find(y)) continue;
    x = find(x);
    y = find(y);
    int z = getlca(x, y);
    downv[y]--;
    downv[z]++;
    upv[x]--;
    upv[z]++;
  }
  memset(seen, 0, sizeof(seen));
  for(int i = 1; i <= n; i++) {
    if(!seen[i]) {
      pii curr = dfsforforce(i, -1);
      assert(curr == pii(0, 0));
    }
  }
  for(int i = 0; i < m; i++) {
    if(find(lhsedge[i]) == find(rhsedge[i])) {
      cout << "B";
      continue;
    }
    if(forced.count(pii(lhsedge[i], rhsedge[i]))) {
      cout << "R";
      continue;
    }
    if(forced.count(pii(rhsedge[i], lhsedge[i]))) {
      cout << "L";
      continue;
    }
    cout << "B";
  }
  cout << "\n";
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7884 KB Output is correct
2 Correct 5 ms 7884 KB Output is correct
3 Correct 5 ms 7884 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 6 ms 7884 KB Output is correct
7 Correct 6 ms 8112 KB Output is correct
8 Correct 6 ms 8012 KB Output is correct
9 Correct 5 ms 7884 KB Output is correct
10 Correct 5 ms 7884 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7884 KB Output is correct
2 Correct 5 ms 7884 KB Output is correct
3 Correct 5 ms 7884 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 6 ms 7884 KB Output is correct
7 Correct 6 ms 8112 KB Output is correct
8 Correct 6 ms 8012 KB Output is correct
9 Correct 5 ms 7884 KB Output is correct
10 Correct 5 ms 7884 KB Output is correct
11 Correct 48 ms 14080 KB Output is correct
12 Correct 56 ms 15888 KB Output is correct
13 Correct 70 ms 18292 KB Output is correct
14 Correct 94 ms 22580 KB Output is correct
15 Correct 110 ms 23924 KB Output is correct
16 Correct 189 ms 29516 KB Output is correct
17 Correct 206 ms 33352 KB Output is correct
18 Correct 257 ms 29892 KB Output is correct
19 Correct 189 ms 34672 KB Output is correct
20 Correct 67 ms 16548 KB Output is correct
21 Correct 57 ms 16696 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7884 KB Output is correct
2 Correct 5 ms 7884 KB Output is correct
3 Correct 5 ms 7884 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 6 ms 7884 KB Output is correct
7 Correct 6 ms 8112 KB Output is correct
8 Correct 6 ms 8012 KB Output is correct
9 Correct 5 ms 7884 KB Output is correct
10 Correct 5 ms 7884 KB Output is correct
11 Correct 48 ms 14080 KB Output is correct
12 Correct 56 ms 15888 KB Output is correct
13 Correct 70 ms 18292 KB Output is correct
14 Correct 94 ms 22580 KB Output is correct
15 Correct 110 ms 23924 KB Output is correct
16 Correct 189 ms 29516 KB Output is correct
17 Correct 206 ms 33352 KB Output is correct
18 Correct 257 ms 29892 KB Output is correct
19 Correct 189 ms 34672 KB Output is correct
20 Correct 67 ms 16548 KB Output is correct
21 Correct 57 ms 16696 KB Output is correct
22 Correct 342 ms 36104 KB Output is correct
23 Correct 304 ms 34556 KB Output is correct
24 Correct 387 ms 34372 KB Output is correct
25 Correct 314 ms 39240 KB Output is correct
26 Correct 313 ms 35640 KB Output is correct
27 Correct 347 ms 34496 KB Output is correct
28 Correct 49 ms 10776 KB Output is correct
29 Correct 94 ms 16140 KB Output is correct
30 Correct 93 ms 16620 KB Output is correct
31 Correct 92 ms 16612 KB Output is correct
32 Correct 185 ms 24084 KB Output is correct