//! The Leader Of Retards Bemola
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define sz(x) (ll) x.size()
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
ll Pow(ll a, ll b, ll md, ll ans = 1) {
for (; b; b >>= 1, a = a * a % md)
if (b & 1)
ans = ans * a % md;
return ans % md;
}
const ll MAXN = 1e5 + 10;
const ll LOG = 18;
const ll MOD = 1e9 + 7;
ll A[MAXN], B[MAXN], P[MAXN], M[MAXN], L[MAXN], ps[MAXN], mark[MAXN], n, m, k, timer;
vector<pll> adj[MAXN]; pll E[MAXN];
void preDFS(ll v, ll p = -1) {
mark[v] = 1;
M[v] = L[v] = ++timer;
for (pll u : adj[v]) {
if (u.S == p) continue;
if (L[u.F] != 0) {
M[v] = min(M[v], L[u.F]);
} else {
preDFS(u.F, u.S);
if (M[u.F] > L[v]) B[u.S] = 1;
M[v] = min(M[v], M[u.F]);
}
}
}
ll Find(ll v) { return P[v] == -1 ? v : P[v] = Find(P[v]); }
void Union(ll u, ll v) {
u = Find(u), v = Find(v);
return (u == v ? void() : void(P[u] = v));
}
void DFS(ll v, ll p = -1) {
mark[v] = 1;
for (pll u : adj[v]) {
if (u.F == p) continue;
DFS(u.F, v);
if (ps[u.F] < 0) {
if (Find(E[u.S].F) == v) A[u.S] = 1;
else A[u.S] = -1;
} else if (ps[u.F] > 0) {
if (Find(E[u.S].F) == v) A[u.S] = -1;
else A[u.S] = 1;
}
ps[v] += ps[u.F];
}
}
int main() {
fill(P, P + MAXN, -1);
scanf("%d%d", &n, &m);
for (ll i = 1; i <= m; i++) {
ll u, v; scanf("%d%d", &u, &v);
adj[v].push_back({u, i});
adj[u].push_back({v, i}); E[i] = {u, v};
}
for (ll i = 1; i <= n; i++) if (mark[i] == 0) preDFS(i);
for (ll i = 1; i <= m; i++) {
if (B[i] == 0) Union(E[i].F, E[i].S);
}
for (ll i = 1; i <= n; i++) adj[i].clear(), adj[i].shrink_to_fit();
for (ll i = 1; i <= m; i++) {
if (B[i]) {
printf("b %d\n", i);
ll u = Find(E[i].F), v = Find(E[i].S);
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
}
scanf("%d", &k);
for (ll i = 1; i <= k; i++) {
ll u, v; scanf("%d%d", &u, &v);
u = Find(u), v = Find(v);
ps[u]++, ps[v]--;
}
fill(mark, mark + MAXN, 0);
for (ll i = 1; i <= n; i++) {
if (mark[Find(i)] == 0) DFS(Find(i));
}
for (ll i = 1; i <= m; i++) {
if (A[i] == 1) printf("R");
else if (A[i] == -1) printf("L");
else printf("B");
}
printf("\n");
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
68 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:70:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | ll u, v; scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
oneway.cpp:89:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
89 | ll u, v; scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
