#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
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;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 3 |
Correct |
1285 ms |
9920 KB |
Output is correct |
| 4 |
Correct |
40 ms |
8124 KB |
Output is correct |
| 5 |
Correct |
63 ms |
8248 KB |
Output is correct |
| 6 |
Correct |
461 ms |
8492 KB |
Output is correct |
| 7 |
Correct |
57 ms |
8176 KB |
Output is correct |
| 8 |
Correct |
43 ms |
8228 KB |
Output is correct |
| 9 |
Correct |
297 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
149 ms |
8120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 3 |
Correct |
1285 ms |
9920 KB |
Output is correct |
| 4 |
Correct |
40 ms |
8124 KB |
Output is correct |
| 5 |
Correct |
63 ms |
8248 KB |
Output is correct |
| 6 |
Correct |
461 ms |
8492 KB |
Output is correct |
| 7 |
Correct |
57 ms |
8176 KB |
Output is correct |
| 8 |
Correct |
43 ms |
8228 KB |
Output is correct |
| 9 |
Correct |
297 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
149 ms |
8120 KB |
Output is correct |
| 11 |
Execution timed out |
3074 ms |
18720 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 3 |
Correct |
1285 ms |
9920 KB |
Output is correct |
| 4 |
Correct |
40 ms |
8124 KB |
Output is correct |
| 5 |
Correct |
63 ms |
8248 KB |
Output is correct |
| 6 |
Correct |
461 ms |
8492 KB |
Output is correct |
| 7 |
Correct |
57 ms |
8176 KB |
Output is correct |
| 8 |
Correct |
43 ms |
8228 KB |
Output is correct |
| 9 |
Correct |
297 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
149 ms |
8120 KB |
Output is correct |
| 11 |
Execution timed out |
3074 ms |
18720 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
