제출 #644425

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