Submission #438489

#	Time	Username	Problem	Language	Result	Execution time	Memory
438489		xiaowuc1	One-Way Streets (CEOI17_oneway)	C++17	30 / 100	3074 ms	18720 KiB

oneway

#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
// 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;
    cerr << "dfs out from " << curr << " to " << out << endl;
    pii cand = dfsforforce(out, curr);
    ret.f += cand.f;
    ret.s += cand.s;
  }
  assert(ret.f <= 0 || ret.s <= 0);
  cerr << "when dfs " << curr << " get ret of " << ret.f << " " << ret.s << endl;
  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) {
  cerr << "merge " << x << " " << y << endl;
  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];

void dfsforcycle(int curr, int edgeIndex, vector<int>& v) {
  instack[curr] = sz(v);
  v.pb(curr);
  seen[curr] = true;
  for(auto out: edges[curr]) {
    if(out.s == edgeIndex) continue;
    if(out.f == curr) continue;
    if(instack[out.f] >= 0) {
      cerr << "claim to have found a cycle" << endl;
      cerr << "edge for cycle is from " << curr << " to " << out.f << endl;
      for(auto out: v) cerr << out << " "; cerr << endl;
      for(int a = instack[out.f]; a + 1 < sz(v); a++) {
        if(!merge(v[a], v[a+1])) continue;
      }
      for(int a = sz(v)-1; a-1 >= instack[out.f]; a--) {
        if(!merge(v[a], v[a-1])) continue;
      }
      continue;
    }
    if(!seen[out.f]) {
      dfsforcycle(out.f, out.s, v);
    }
  }
  assert(instack[curr] == sz(v) - 1);
  instack[curr] = -1;
  assert(v.back() == curr);
  v.pop_back();
}

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;
      dfsforcycle(i, -1, v);
    }
  }
  for(int i = 0; i < m; i++) {
    cerr << "old edge was " << lhsedge[i] << " " << rhsedge[i] << endl;
    lhsedge[i] = find(lhsedge[i]);
    rhsedge[i] = find(rhsedge[i]);
    cerr << "edge is now " << lhsedge[i] << " " << rhsedge[i] << endl;
  }
  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;
    cerr << "old query " << x << " " << y << endl;
    if(find(x) == find(y)) continue;
    x = find(x);
    y = find(y);
    int z = getlca(x, y);
    cerr << "establish path " << x << " " << z << " " << y << endl;
    downv[y]--;
    downv[z]++;
    upv[x]--;
    upv[z]++;
  }
  memset(seen, 0, sizeof(seen));
  for(int i = 1; i <= n; i++) {
    if(!seen[i]) {
      cerr << "init dfs from " << i << endl;
      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();
}

Compilation message (stderr)

oneway.cpp: In function 'void dfsforcycle(int, int, std::vector<int>&)':
oneway.cpp:113:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  113 |       for(auto out: v) cerr << out << " "; cerr << endl;
      |       ^~~
oneway.cpp:113:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  113 |       for(auto out: v) cerr << out << " "; cerr << endl;
      |                                            ^~~~

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