#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < k; i++)
#define pb push_back
typedef long long ll;
typedef pair<int , int> pii;
typedef vector<int> vi;
template<typename S, typename T>
inline bool smin(S &l, T r) { return l < r ? 0 : (l = r, 1); }
template<typename S, typename T>
inline bool smax(S &l, T r) { return r < l ? 0 : (l = r, 1); }
constexpr int N = 1e5 + 10;
int n, m, p, a[N], b[N], COLOR, val[N];
vi adj[N], adj2[N];
int h[N], dp[N], inp[N], col[N];
bitset<N> mark;
void dfs2(int v, int cl, int id = -1) {
mark[v] = true;
if (v > 1 && col[v]) {
adj2[cl].pb(inp[v]);
cl = col[v];
}
col[v] = cl;
for (auto e : adj[v]) {
int u = a[e] ^ b[e] ^ v;
if (!mark[u])
dfs2(u , cl , e);
}
}
void dfs(int v, int id = m) {
mark[v] = true;
dp[v] = h[v];
for (auto e : adj[v]) {
if (e == id) continue;
int u = a[e] ^ b[e] ^ v;
if (mark[u])
smin(dp[v] , h[u]);
else {
h[u] = h[v] + 1;
dfs(u, e);
smin(dp[v] , dp[u]);
}
}
if (dp[v] == h[v]) {
col[v] = ++COLOR;
inp[v] = id;
}
}
char res[N];
void dfs3(int v, int id = m) {
for (auto e : adj2[v]) {
int u = v ^ col[a[e]] ^ col[b[e]];
dfs3(u, e);
val[v] += val[u];
}
if (val[v] == 0) return;
res[id] = (val[v] < 0) == (col[b[id]] == v) ? 'R' : 'L';
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
rep(i , 0 , m) {
cin >> a[i] >> b[i];
adj[a[i]].pb(i);
adj[b[i]].pb(i);
}
dfs(1);
mark.reset();
dfs2(1 , COLOR);
cin >> p;
rep(i , 0 , p) {
int u , v;
cin >> u >> v;
u = col[u] , v = col[v];
if (u == v) continue;
val[u]++;
val[v]--;
}
memset(res , 'B', sizeof(res));
dfs3(COLOR);
rep(i , 0 , m)
cout << res[i];
cout << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
