이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int, int > PII;
#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekek
#define left(v) v << 1
#define right(v) v << 1 | 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
const ll ool = 1e18 + 9;
const int N = 2e5 + 6, oo = 1e9 + 9, base = 1e9 + 7;
int n, m, Q, cnt, timer, tin[N], d[N], col[N], val[N], dp[N], a[N], b[N];
char ans[N];
bool u[N], bridge[N];
vector < PII > g[N], g2[N];
vector < int > vec;
void dfs(int v, int par) {
u[v] = 1;
tin[v] = ++timer;
d[v] = tin[v];
for (auto it : g[v]) {
int to = it.F;
if (it.S == par) continue;
if (u[to]) {
d[v] = min(d[v], tin[to]);
}
else {
int cur = sz(vec);
dfs(to, it.S);
d[v] = min(d[v], d[to]);
if (d[to] > tin[v]) {
bridge[it.S] = 1;
++cnt;
while (sz(vec) != cur) {
col[vec.back()] = cnt;
vec.pop_back();
}
}
}
}
vec.eb(v);
}
void calc(int v) {
u[v] = 1;
for (auto it : g2[v]) {
int to = it.F;
if (u[to]) continue;
calc(to);
dp[v] += dp[to];
if (dp[to] < 0) ans[it.S] = (col[a[it.S]] == v ? 'R' : 'L');
if (dp[to] == 0) ans[it.S] = 'B';
if (dp[to] > 0) ans[it.S] = (col[a[it.S]] == v ? 'L' : 'R');
}
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
#ifdef krauch
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m;
forn(i, 1, m) {
int x, y;
cin >> x >> y;
g[x].eb(y, i);
g[y].eb(x, i);
a[i] = x;
b[i] = y;
}
cin >> Q;
forn(i, 1, Q) {
int x, y;
cin >> x >> y;
val[x]++;
val[y]--;
}
forn(i, 1, n) {
if (!u[i]) {
dfs(i, 0);
++cnt;
while (sz(vec)) {
col[vec.back()] = cnt;
vec.pop_back();
}
}
}
forn(i, 1, m) {
if (!bridge[i]) {
ans[i] = 'B';
continue;
}
g2[col[a[i]]].eb(col[b[i]], i);
g2[col[b[i]]].eb(col[a[i]], i);
}
forn(i, 1, n) {
u[i] = 0;
dp[col[i]] += val[i];
}
forn(i, 1, cnt) {
if (!u[i]) calc(i);
}
forn(i, 1, m) cout << ans[i];
cout << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |