#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(ll i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e endl
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define anc ancestor
const int MAXN = 100000;
//500,000,000 operations
int N, M, P, counter, dp[MAXN], num[MAXN], low[MAXN], parent[MAXN], N2;
int comp[MAXN], edges[MAXN][2], par[MAXN], anc[MAXN][20], q[MAXN][2], dep[MAXN];
bool visited[MAXN], up[MAXN], down[MAXN];
multiset <int> adj[MAXN];
vector <int> adj2[MAXN];
set<pair<int, int> > out; ///BRIDGES IN OUT
void dfs(int x) {
if (visited[x]) return;
visited[x] = true;
//w<< x s parent<<e;
num[x] = low[x] = (++counter);
int children = 0;
for (int y : adj[x]) {
if (!visited[y]) {
children++;
parent[y] = x;
dfs(y);
low[x] = min(low[x], low[y]);
if (low[y] > num[x] && adj[x].count(y) < 2) out.insert(mp(min(x, y), max(x, y)) );
}
else if (parent[x] != y) {
low[x] = min(low[x], num[y]);
}
}
}
void go(int at) {
if (visited[at]) return;
comp[at] = N2;
visited[at] = true;
for (int i: adj[at]) if (out.find(mp(min(at, i), max(at, i))) == out.end() ) {
//w<< at+1 s "to" s i+1<<e;
go(i);
}
}
int LCA(int A, int B) {
if (dep[A] > dep[B]) swap(A, B);
int d = dep[B] - dep[A];
For (i, 0, 18) {
if (d&(1<<i) ) B = ancestor[B][i];
}
if (A == B) return A;
for (int i=17; i>= 0; i--) {
if (ancestor[A][i] != ancestor[B][i]) {
A = ancestor[A][i];
B = ancestor[B][i];
}
}
return anc[A][0];
}
void go2(int at, int up) {
par[at] = anc[at][0] = up;
dep[at] = 1+dep[up];
for (int i: adj2[at]) if (i != up) go2(i, at);
}
void adjust(int at) {
for (int i: adj2[at]) if (i != par[at]) adjust(i), dp[at] += dp[i];
}
int main() {
//ifstream cin ("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
ffi low[i] = 10000000;
ffj {
int a, b; cin >> a >> b; a--; b--;
edges[j][0] = a, edges[j][1] = b;
adj[a].insert(b);
adj[b].insert(a);
}
ffi dfs(i);
///BRIDGES IN OUT
//w<< out.size()<<e; for (auto i: out) w<< (i).a+1 s (i).b+1<<e;
ffi visited[i] = false;
ffi if (!visited[i]) {
go(i);
N2++;
}
//ffi w<< i+1 s ":" s comp[i]+1<<e;
ffi for (int j: adj[i]) if (comp[i] != comp[j]) adj2[comp[i]].pb(comp[j]);
//For (i, 0, N2) {for (auto j: adj2[i]) w<< j+1 s " "; w<<e;}
N = N2;
dep[0] = -1, go2(0, 0);
For (k, 0, 19) ffi anc[i][k+1] = anc[anc[i][k]][k];
cin >> P;
For (p, 0, P) {
int a, b; cin >> a >> b; a--; b--; a = comp[a], b = comp[b];
q[p][0] = a, q[p][1] = b;
if (a == b) continue;
int c = LCA(a, b);
dp[a] += 1;
dp[c] -= 1;
}
adjust(0);
ffi {
assert(dp[i] >= 0);
if (dp[i] != 0) up[i] = true, dp[i] = 0;
}
For (p, 0, P) {
int a = q[p][0], b = p[q][1];
if (a == b) continue;
int c = LCA(a, b);
dp[b] += 1;
dp[c] -= 1;
}
adjust(0);
ffi if (dp[i] != 0) down[i] = true;
//ffi w<< up[i] s down[i]<<e;
ffj {
int a = comp[edges[j][0]], b = comp[edges[j][1]];
if (a == b) {w<< 'B'; continue;}
//w<< a s b<<e;
if (b == par[a]) {
if (up[a]) w<< 'R';
else if (down[a]) w<< 'L';
else w<< 'B';
}
else {
if (up[b]) w<< 'L';
else if (down[b]) w<< 'R';
else w<< 'B';
}
}
w<<e;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
