이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
VOI23 gold medal
*/
const int N = 1e5 + 5;
int n, m, p, h[N], P[N][17], pos[N], s[N], c[N], tin[N], low[N], bridge[N], scc[N], cnt = 0, cnt1 = 0;
pi f[N];
pi e[N];
vi adj[N], adj1[N];
void upd(int ps, pi v) { for (int i = ps; i <= cnt; i += (i & -i)) { f[i].st += v.st; f[i].nd += v.nd; } }
pi get(int ps) { pi rs = {0, 0}; for (int i = ps; i >= 1; i -= (i & -i)) { rs.st += f[i].st; rs.nd += f[i].nd; } return rs; }
void dfs(int u, int p) {
tin[u] = low[u] = ++cnt;
EACH(j, adj[u]) {
if (j == p) continue;
int v = (e[j].st == u? e[j].nd : e[j].st);
if (tin[v]) low[u] = min(low[u], tin[v]);
else {
dfs(v, j);
low[u] = min(low[u], low[v]);
if (low[v] > tin[u]) bridge[j] = 1;
}
}
}
void dfs1(int u) {
EACH(j, adj[u]) {
int v = (e[j].st == u? e[j].nd : e[j].st);
if (scc[v]) continue;
if (bridge[j]) {
scc[v] = ++cnt;
adj1[scc[u]].pb(scc[v]);
adj1[scc[v]].pb(scc[u]);
dfs1(v);
}
else {
scc[v] = scc[u];
dfs1(v);
}
}
}
void dfs2(int u, int p) {
c[u] = 1;
h[u] = h[p] + 1;
P[u][0] = p;
pos[u] = ++cnt1;
s[u] = 1;
EACH(v, adj1[u]) {
if (v == p) continue;
dfs2(v, u);
}
}
void build() {
FOR(j, 1, 16)
FOR(i, 1, cnt)
P[i][j] = P[P[i][j - 1]][j - 1];
}
int lca(int a, int b) {
if (h[a] > h[b]) swap(a, b);
int diff = h[b] - h[a];
FOR(i, 0, 16)
if (diff & (1 << i))
b = P[b][i];
if (a == b) return a;
FOS(i, 16, 0)
if (P[a][i] != P[b][i]) {
a = P[a][i];
b = P[b][i];
}
return P[a][0];
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> m;
FOR(i, 1, m) {
int u, v;
cin >> u >> v;
e[i] = {u, v};
adj[u].pb(i);
adj[v].pb(i);
}
FOR(i, 1, n) {
if (tin[i]) continue;
dfs(i, 0);
}
cnt = 0;
FOR(i, 1, n) {
if (scc[i]) continue;
scc[i] = ++cnt;
dfs1(i);
}
FOR(i, 1, cnt) {
if (c[i]) continue;
dfs2(i, 0);
}
build();
cin >> p;
FOR(i, 1, p) {
int x, y;
cin >> x >> y;
x = scc[x];
y = scc[y];
if (x == y) continue;
int LCA = lca(x, y);
upd(pos[x], {1, 0});
upd(pos[y], {0, 1});
upd(pos[LCA], {-1, -1});
}
FOR(i, 1, m)
if (!bridge[i]) cout << 'B';
else {
int u = e[i].st, v = e[i].nd;
u = scc[u];
v = scc[v];
if (P[u][0] == v) swap(u, v);
pi f = get(pos[v] + s[v] - 1), s = get(pos[v] - 1);
f.st -= s.st;
f.nd -= s.nd;
if (!f.st && !f.nd) cout << 'B';
else if (f.st) {
if (scc[e[i].st] == u) cout << 'L';
else cout << 'R';
}
else {
if (scc[e[i].st] == u) cout << 'R';
else cout << 'L';
}
}
return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
/*
From Benq:
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
컴파일 시 표준 에러 (stderr) 메시지
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
32 | #define EACH(i, x) for (auto &(i) : (x))
| ^
oneway.cpp:50:2: note: in expansion of macro 'EACH'
50 | EACH(j, adj[u]) {
| ^~~~
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
32 | #define EACH(i, x) for (auto &(i) : (x))
| ^
oneway.cpp:62:2: note: in expansion of macro 'EACH'
62 | EACH(j, adj[u]) {
| ^~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:32:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
32 | #define EACH(i, x) for (auto &(i) : (x))
| ^
oneway.cpp:83:2: note: in expansion of macro 'EACH'
83 | EACH(v, adj1[u]) {
| ^~~~
oneway.cpp: In function 'void build()':
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:89:2: note: in expansion of macro 'FOR'
89 | FOR(j, 1, 16)
| ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:90:2: note: in expansion of macro 'FOR'
90 | FOR(i, 1, cnt)
| ^~~
oneway.cpp: In function 'int lca(int, int)':
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:96:2: note: in expansion of macro 'FOR'
96 | FOR(i, 0, 16)
| ^~~
oneway.cpp:31:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
| ^
oneway.cpp:100:2: note: in expansion of macro 'FOS'
100 | FOS(i, 16, 0)
| ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:112:5: note: in expansion of macro 'FOR'
112 | FOR(i, 1, m) {
| ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:119:5: note: in expansion of macro 'FOR'
119 | FOR(i, 1, n) {
| ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:124:5: note: in expansion of macro 'FOR'
124 | FOR(i, 1, n) {
| ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:129:5: note: in expansion of macro 'FOR'
129 | FOR(i, 1, cnt) {
| ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:135:5: note: in expansion of macro 'FOR'
135 | FOR(i, 1, p) {
| ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
oneway.cpp:146:5: note: in expansion of macro 'FOR'
146 | FOR(i, 1, m)
| ^~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
