//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef __APPLE__
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct bridges_two_edge_connected_components {
static const int max_n = -1;
int m = 0;
vector<vector<pair<int, int> > > g;
vector<bool> visited, is_bridge;
vector<int> tin, low;
int timer;
void init(int n) {
clear(n);
g.assign(n, {});
}
void clear(int n) {
m = 0;
g.clear();
visited.clear(); is_bridge.clear();
tin.clear(); low.clear();
timer = 0;
}
void add_edge(int a, int b) {
g[a].pb({b, m});
g[b].pb({a, m});
m++;
}
void dfs_bridges(int v, int p = -1) {
visited[v] = true;
tin[v] = low[v] = timer++;
for (auto& to : g[v]) {
if (to.se == p) continue;
if (visited[to.fi]) {
low[v] = min(low[v], tin[to.fi]);
} else {
dfs_bridges(to.fi, to.se);
low[v] = min(low[v], low[to.fi]);
if (low[to.fi] > tin[v]) is_bridge[to.se] = true;
}
}
}
vector<bool> find_bridges(int n) {
is_bridge.assign(m, false);
timer = 0;
visited.assign(n, false);
tin.assign(n, -1);
low.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs_bridges(i);
}
return is_bridge;
}
vector<int> two_edge_component;
int comp_num;
void dfs_components(int v) {
two_edge_component[v] = comp_num;
for(auto& to : g[v])
if(two_edge_component[to.fi] == -1 && !is_bridge[to.se])
dfs_components(to.fi);
}
vector<int> find_two_edge_component_nums(int n) {
find_bridges(n);
two_edge_component.assign(n, -1);
comp_num = 0;
for(int i = 0; i < n; i++)
if(two_edge_component[i] == -1) {
dfs_components(i);
comp_num++;
}
return two_edge_component;
}
vector<vector<int> > find_two_edge_components(int n) {
auto component_nums = find_two_edge_component_nums(n);
int am_components = *max_element(all(component_nums)) + 1;
vector<vector<int> > components(am_components);
for(int i = 0; i < n; i++) components[component_nums[i]].pb(i);
return components;
}
};
const int max_n = 1e5, K = 18;
vector<pair<int, int> > g[max_n];
int tin[max_n], tout[max_n];
int up[max_n][K];
int timer = 0;
int dep[max_n];
void predfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < K; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto &x: g[v])
if (x.fi != p) {
dep[x.fi] = dep[v] + 1;
predfs(x.fi, v);
}
tout[v] = ++timer;
}
int jump(int x, int d) {
for (int i = 0; i < K; i++)
if (((d >> i) & 1)) {
x = up[x][i];
}
return x;
}
bool ancester(int a, int b) {
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b) {
if (ancester(a, b)) return a;
if (ancester(b, a)) return b;
for (int i = K - 1; i >= 0; i--)
if (!ancester(up[a][i], b))
a = up[a][i];
return up[a][0];
}
int kek[max_n][2];
int par_edge[max_n];
bool used[max_n];
void dfs(int v, int p) {
used[v] = true;
for(auto& to : g[v])
if(to.fi != p) {
par_edge[to.fi] = to.se;
dfs(to.fi, v);
kek[v][0] += kek[to.fi][0];
kek[v][1] += kek[to.fi][1];
}
}
void solve() {
int n, m;
cin >> n >> m;
bridges_two_edge_connected_components graph;
graph.init(n);
vector<pair<int, int> > edges(m);
for(auto& x : edges) {
cin >> x.fi >> x.se;
x.fi--; x.se--;
graph.add_edge(x.fi, x.se);
}
auto component_nums = graph.find_two_edge_component_nums(n);
for(int i = 0; i < m; i++) {
int u = component_nums[edges[i].fi];
int v = component_nums[edges[i].se];
if(u != v) {
g[u].pb({v, i});
g[v].pb({u, i});
}
}
for(int i = 0; i < n; i++) par_edge[i] = -1;
predfs(0, 0);
int p; cin >> p;
while(p--) {
int s, t;
cin >> s >> t;
s--; t--;
s = component_nums[s]; t = component_nums[t];
if(s == t) continue;
if(ancester(s, t)) {
kek[t][1]++;
kek[s][1]--;
} else if(ancester(t, s)) {
kek[s][0]++;;
kek[t][0]--;
} else {
int clca = lca(s, t);
kek[s][0]++;
kek[clca][0]--;
kek[t][1]++;
kek[clca][1]--;
}
}
for(int i = 0; i < n; i++)
if(!g[i].empty() && !used[i])
dfs(i, i);
string ans = string(m, 'B');
for(int i = 0; i < n; i++)
if(par_edge[i] != -1) {
int from = i;
if(kek[i][0]) ans[par_edge[i]] = (component_nums[edges[par_edge[i]].fi] == from ? 'R' : 'L');
else if(kek[i][1]) ans[par_edge[i]] = (component_nums[edges[par_edge[i]].fi] == from ? 'L' : 'R');
}
cout << ans;
}
signed main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
}
/*
KIVI
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2676 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2804 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2676 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2804 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
39 ms |
9216 KB |
Output is correct |
| 12 |
Correct |
38 ms |
10340 KB |
Output is correct |
| 13 |
Correct |
50 ms |
12416 KB |
Output is correct |
| 14 |
Correct |
56 ms |
16644 KB |
Output is correct |
| 15 |
Incorrect |
64 ms |
18512 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2676 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2804 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
39 ms |
9216 KB |
Output is correct |
| 12 |
Correct |
38 ms |
10340 KB |
Output is correct |
| 13 |
Correct |
50 ms |
12416 KB |
Output is correct |
| 14 |
Correct |
56 ms |
16644 KB |
Output is correct |
| 15 |
Incorrect |
64 ms |
18512 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
