#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define loop(i,n) for(int i = 0;i < (n);i++)
#define all(A) A.begin(),A.end()
#define pb push_back
#define mp make_pair
#define sz(A) ((int)A.size())
typedef std::vector<int> vi;
typedef std::pair<int,int> pi;
typedef std::vector<pi> vp;
typedef long long ll;
#define popcnt(x) __builtin_popcount(x)
#define LSOne(x) ((x) & (-(x)))
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prArr(A,n,t) cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define PRESTDIO() cin.tie(0),cerr.tie(0),ios_base::sync_with_stdio(0)
#define what_is(x) cerr << #x << " is " << x << endl
#define bit_lg(x) (assert(x > 0),__builtin_ffsll(x) - 1)
const double PI = acos(-1);
template<class A,class B>
std::ostream& operator << (std::ostream& st,const std::pair<A,B> p) {
st << "(" << p.first << ", " << p.second << ")";
return st;
}
void tc();
auto test_cases = []() {
int T; scanf("%d", &T);
while(T--) tc();
};
using namespace std;
const int MAXN = 100*1000 + 10;
int dfs_num[MAXN], dfs_low[MAXN], dfs_time;
list<int> E[MAXN];
vi fr, to;
vector<bool> isBridge;
int n, m, p;
void dfs(int u, int ie){
dfs_low[u] = dfs_num[u] = dfs_time++;
for(int e : E[u]) if(e != ie) {
int v = fr[e] + to[e] - u;
if(dfs_num[v] == -1){
dfs(v, e);
if(dfs_low[v] > dfs_num[u]) {
isBridge[e] = true;
}
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
} else {
dfs_low[u] = min(dfs_low[u], dfs_num[v]);
}
}
}
int id[MAXN], W[MAXN];
int find(int a){
return id[a] = (a == id[a]) ? a : find(id[a]);
}
void join(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
if(W[a] < W[b]) swap(a, b);
W[a] += W[b];
id[b] = a;
E[a].splice(E[a].end(), E[b]);
}
const int MAXLG = 20;
int depth[MAXN], P[MAXN][MAXLG];
int dfs_in[MAXN], dfs_out[MAXN];
void dfs2(int u, int p) {
dfs_in[u] = dfs_num[u] = dfs_time++;
depth[u] = depth[p] + 1;
P[u][0] = p;
loop(k, MAXLG - 1) P[u][k + 1] = P[P[u][k]][k];
for(int e : E[u]) {
int a = fr[e], b = to[e];
if(find(a) != u) swap(a, b);
if(find(b) == u || find(b) == p) continue;
dfs2(find(b), u);
}
dfs_out[u] = dfs_time - 1;
}
bool inSubTree(int a,int b){
return dfs_in[b] <= dfs_in[a] && dfs_in[a] <= dfs_out[b];
}
int lca(int a,int b){
if(depth[a] > depth[b]) swap(a,b);
if(inSubTree(b,a)) return a;
int k = MAXLG - 1;
while(a != b){
if(depth[a] > depth[b]) swap(a,b);
while(k && inSubTree(a,P[b][k])) k--;
b = P[b][k];
}
return a;
}
int val[MAXN];
vi edgeVal;
int dfs3(int u, int p){
int ret = val[u];
dfs_num[u] = 1;
for(int e : E[u]) {
int a = fr[e], b = to[e];
if(find(a) != u) swap(a, b);
if(find(b) == u || find(b) == p) continue;
int tmp = dfs3(find(b), u);
edgeVal[e] = tmp;
ret += tmp;
}
return ret;
}
int main(){
#ifdef HOME
freopen("in.in", "r", stdin);
#endif
scanf("%d %d", &n, &m);
loop(e, m){
int a, b; scanf("%d %d", &a, &b);
fr.push_back(a);
to.push_back(b);
isBridge.push_back(false);
E[a].push_back(e);
E[b].push_back(e);
}
memset(dfs_num, -1, sizeof dfs_num);
for(int i = 1; i <= n; i++) if(dfs_num[i] == -1) dfs(i, -1);
fill(W, W + n + 1, 1);
iota(id, id + n + 1, 0);
loop(e, m) if(!isBridge[e]) join(fr[e], to[e]);
memset(dfs_num, -1, sizeof dfs_num);
dfs_time = 0;
for(int i = 1; i <= n; i++) if(dfs_num[i] == -1) dfs2(i, 0);
dfs_out[0] = dfs_time;
edgeVal.resize(m, 0);
scanf("%d", &p);
while(p--){
int a, b; scanf("%d %d", &a, &b);
int p = lca(a, b);
val[a]++;
val[p]--;
val[b]--;
val[p]++;
}
memset(dfs_num, -1, sizeof dfs_num);
for(int i = 1; i <= n; i++) if(dfs_num[i] == -1) dfs3(i, 0);
loop(e, m) {
if(!isBridge[e] || edgeVal[e] == 0) putchar('B');
else {
int a0 = find(fr[e]), b0 = find(to[e]);
int a = a0, b = b0;
if(depth[a] > depth[b]) swap(a, b);
if(edgeVal[e] > 0) swap(a, b);
putchar("LR"[a == a0]);
}
}
puts("");
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | int a, b; scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
oneway.cpp:147:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
147 | int a, b; scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3144 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3144 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3144 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
