oj.uz

답안 #438494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438494 2021-06-28T06:00:06 Z xiaowuc1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 2650 ms 52292 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);
    }
  }
  cerr << "finish dfs " << curr << ": " << ret << endl;
  cerr << "cycle compensation factor of " << sz(v)-1 << " detected" << endl;
  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();
  cerr << "exiting dfs of " << curr << " with cycle count of " << ret << endl;
  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 5 ms 7884 KB Output is correct
2 Correct 5 ms 7884 KB Output is correct
3 Correct 18 ms 8004 KB Output is correct
4 Correct 29 ms 8124 KB Output is correct
5 Correct 28 ms 8140 KB Output is correct
6 Correct 17 ms 8028 KB Output is correct
7 Correct 29 ms 8172 KB Output is correct
8 Correct 28 ms 8140 KB Output is correct
9 Correct 17 ms 8000 KB Output is correct
10 Correct 16 ms 8004 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7884 KB Output is correct
2 Correct 5 ms 7884 KB Output is correct
3 Correct 18 ms 8004 KB Output is correct
4 Correct 29 ms 8124 KB Output is correct
5 Correct 28 ms 8140 KB Output is correct
6 Correct 17 ms 8028 KB Output is correct
7 Correct 29 ms 8172 KB Output is correct
8 Correct 28 ms 8140 KB Output is correct
9 Correct 17 ms 8000 KB Output is correct
10 Correct 16 ms 8004 KB Output is correct
11 Correct 452 ms 16196 KB Output is correct
12 Correct 719 ms 20328 KB Output is correct
13 Correct 1188 ms 25024 KB Output is correct
14 Correct 1870 ms 32476 KB Output is correct
15 Correct 2103 ms 34936 KB Output is correct
16 Correct 2386 ms 40924 KB Output is correct
17 Correct 2432 ms 45132 KB Output is correct
18 Correct 2344 ms 41500 KB Output is correct
19 Correct 2400 ms 46408 KB Output is correct
20 Correct 1191 ms 23056 KB Output is correct
21 Correct 1147 ms 23236 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7884 KB Output is correct
2 Correct 5 ms 7884 KB Output is correct
3 Correct 18 ms 8004 KB Output is correct
4 Correct 29 ms 8124 KB Output is correct
5 Correct 28 ms 8140 KB Output is correct
6 Correct 17 ms 8028 KB Output is correct
7 Correct 29 ms 8172 KB Output is correct
8 Correct 28 ms 8140 KB Output is correct
9 Correct 17 ms 8000 KB Output is correct
10 Correct 16 ms 8004 KB Output is correct
11 Correct 452 ms 16196 KB Output is correct
12 Correct 719 ms 20328 KB Output is correct
13 Correct 1188 ms 25024 KB Output is correct
14 Correct 1870 ms 32476 KB Output is correct
15 Correct 2103 ms 34936 KB Output is correct
16 Correct 2386 ms 40924 KB Output is correct
17 Correct 2432 ms 45132 KB Output is correct
18 Correct 2344 ms 41500 KB Output is correct
19 Correct 2400 ms 46408 KB Output is correct
20 Correct 1191 ms 23056 KB Output is correct
21 Correct 1147 ms 23236 KB Output is correct
22 Correct 2650 ms 49228 KB Output is correct
23 Correct 2586 ms 47540 KB Output is correct
24 Correct 2510 ms 47152 KB Output is correct
25 Correct 2489 ms 52292 KB Output is correct
26 Correct 2512 ms 48612 KB Output is correct
27 Correct 2448 ms 47500 KB Output is correct
28 Correct 46 ms 11960 KB Output is correct
29 Correct 1183 ms 23832 KB Output is correct
30 Correct 1197 ms 24616 KB Output is correct
31 Correct 1190 ms 24256 KB Output is correct
32 Correct 1589 ms 33236 KB Output is correct