oj.uz

Submission #438496

# Submission time Handle Problem Language Result Execution time Memory
438496 2021-06-28T06:03:19 Z xiaowuc1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 380 ms 39252 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) {
      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));
    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

# Verdict Execution time Memory Grader output
1 Correct 5 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 6 ms 8012 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 5 ms 7884 KB Output is correct
7 Correct 7 ms 8140 KB Output is correct
8 Correct 6 ms 8012 KB Output is correct
9 Correct 5 ms 7884 KB Output is correct
10 Correct 6 ms 7884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 6 ms 8012 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 5 ms 7884 KB Output is correct
7 Correct 7 ms 8140 KB Output is correct
8 Correct 6 ms 8012 KB Output is correct
9 Correct 5 ms 7884 KB Output is correct
10 Correct 6 ms 7884 KB Output is correct
11 Correct 49 ms 14096 KB Output is correct
12 Correct 67 ms 15868 KB Output is correct
13 Correct 82 ms 18348 KB Output is correct
14 Correct 114 ms 22668 KB Output is correct
15 Correct 116 ms 24052 KB Output is correct
16 Correct 240 ms 29336 KB Output is correct
17 Correct 219 ms 33260 KB Output is correct
18 Correct 207 ms 29876 KB Output is correct
19 Correct 200 ms 34596 KB Output is correct
20 Correct 58 ms 16440 KB Output is correct
21 Correct 78 ms 16708 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 6 ms 8012 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 5 ms 7884 KB Output is correct
7 Correct 7 ms 8140 KB Output is correct
8 Correct 6 ms 8012 KB Output is correct
9 Correct 5 ms 7884 KB Output is correct
10 Correct 6 ms 7884 KB Output is correct
11 Correct 49 ms 14096 KB Output is correct
12 Correct 67 ms 15868 KB Output is correct
13 Correct 82 ms 18348 KB Output is correct
14 Correct 114 ms 22668 KB Output is correct
15 Correct 116 ms 24052 KB Output is correct
16 Correct 240 ms 29336 KB Output is correct
17 Correct 219 ms 33260 KB Output is correct
18 Correct 207 ms 29876 KB Output is correct
19 Correct 200 ms 34596 KB Output is correct
20 Correct 58 ms 16440 KB Output is correct
21 Correct 78 ms 16708 KB Output is correct
22 Correct 380 ms 36152 KB Output is correct
23 Correct 354 ms 34384 KB Output is correct
24 Correct 371 ms 34324 KB Output is correct
25 Correct 331 ms 39252 KB Output is correct
26 Correct 353 ms 35652 KB Output is correct
27 Correct 319 ms 34476 KB Output is correct
28 Correct 45 ms 10844 KB Output is correct
29 Correct 93 ms 16124 KB Output is correct
30 Correct 97 ms 16812 KB Output is correct
31 Correct 82 ms 16560 KB Output is correct
32 Correct 169 ms 24096 KB Output is correct