#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e12;
/***************************CEOI 17 Day 1 P1*************************************/
template<int NSZ, int ESZ> struct BCC {
int NN, MM; // Nodes, Edges
void init(int n, int m) {
NN = n, MM = m;
}
v<pii> adj[NSZ];
int edge[ESZ][2];
void addEdge(int a, int b, int id) {
edge[id][0] = a, edge[id][1] = b;
adj[a].push_back({ b,id }), adj[b].push_back({ a,id });
}
bool bridge[ESZ];
int lo[NSZ], ind[NSZ], t = 0;
void tarjan(int cur, int par = -1) {
ind[cur] = lo[cur] = t++;
for (pii yi : adj[cur]) {
int nex = yi.first, id = yi.second;
if (id == par) continue;
if (ind[nex] == -1) {
tarjan(nex, id);
lo[cur] = min(lo[cur], lo[nex]);
if (lo[nex]>ind[cur]) bridge[id] = 1;
}
else lo[cur] = min(lo[cur], ind[nex]);
}
}
void findBridges() {
memset(ind, -1, sizeof ind);
memset(lo, 0, sizeof lo);
memset(bridge, 0, sizeof bridge);
FOR(i, 0, NN) if (ind[i] == -1)
tarjan(i);
}
bool vis[NSZ];
int comp[NSZ], NC = 0;
v<pii> adjc[NSZ]; // [from] = {to, id}
void components(int cur, int c) {
vis[cur] = 1, comp[cur] = c;
for (pii yi : adj[cur]) {
int nex = yi.first, id = yi.second;
if (!vis[nex] && !bridge[id]) components(nex, c);
}
}
void findComp() {
memset(comp, -1, sizeof comp);
memset(vis, 0, sizeof vis);
FOR(i, 0, NN) if (!vis[i])
components(i, NC++);
FOR(i, 0, MM) if (bridge[i]) {
int ca = comp[edge[i][0]], cb = comp[edge[i][1]];
//assert(ca!=cb);
adjc[ca].push_back({ cb,i }), adjc[cb].push_back({ ca,i });
}
}
};
BCC<100000, 100000> bcc;
int N, M, depth[100000];
string ans;
pii par[100000]; // {node, edge id}
namespace LCA {
const int MAXN = 100000, LOG = 16;
int anc[MAXN][LOG];
void setup(int N) {
for (int j = 1; j < LOG; j++) for (int i = 0; i < N; i++)
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
int diff = depth[x] - depth[y];
for (int i = LOG - 1; i >= 0; i--) if (diff >> i & 1)
x = anc[x][i];
if (x == y) return x;
for (int i = LOG - 1; i >= 0; i--) if (anc[x][i] != anc[y][i])
x = anc[x][i], y = anc[y][i];
return anc[x][0];
}
}
void dfsDepths(int x, int p, int d) {
LCA::anc[x][0] = p, depth[x] = d;
for (pii c : bcc.adjc[x]) if (c.first != p) {
par[c.first] = mp(x, c.second);
dfsDepths(c.first, x, d + 1);
}
}
int direction[100000];
void direct(int x, int g, int d) {
if (x == g) return;
if (direction[x] != 0)
assert(direction[x] == d);
else {
direction[x] = d;
pii myed;
if (d == -1) // x, pars
myed = { x, par[x].first };
else // par, x
myed = { par[x].first, x };
pii orded = mp(bcc.comp[bcc.edge[par[x].second][0]], bcc.comp[bcc.edge[par[x].second][1]]);
if (myed == orded)
ans[par[x].second] = 'R';
else if (myed == mp(orded.second, orded.first))
ans[par[x].second] = 'L';
else
assert(0);
direct(par[x].first, g, d);
}
}
int main() {
io();
cin >> N >> M;
bcc.init(N, M);
FOR(i, 0, M) {
int a, b; cin >> a >> b;
bcc.addEdge(a - 1, b - 1, i);
}
bcc.findBridges();
ans.resize(M);
FOR(i, 0, M)
if (!bcc.bridge[i])
ans[i] = 'B';
bcc.findComp();
memset(depth, -1, sizeof depth);
FOR(i, 0, bcc.NC) if (depth[i] == -1)
dfsDepths(i, -1, 0);
LCA::setup(bcc.NC);
memset(direction, 0, sizeof direction);
int p; cin >> p;
FOR(i, 0, p) {
int a, b; cin >> a >> b;
a = bcc.comp[a - 1], b = bcc.comp[b - 1];
int c = LCA::lca(a, b);
direct(a, c, -1), direct(b, c, 1);
}
// all p
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
