제출 #42961

#제출 시각아이디문제언어결과실행 시간메모리
42961krauchOne-Way Streets (CEOI17_oneway)C++14
100 / 100
133 ms55920 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...