제출 #974174

#제출 시각아이디문제언어결과실행 시간메모리
974174duckindogOne-Way Streets (CEOI17_oneway)C++17
0 / 100
3 ms8540 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int n, m, p; int from[N], to[N]; vector<pair<int, bool>> ad[N]; int a[N], b[N]; namespace BCC { vector<int> ad[N]; int low[N], num[N], it; stack<int> st; int bcc[N], cc; void dfs(int u, int p = -1) { low[u] = num[u] = ++it; st.push(u); bool pass = false; for (const auto& v : ad[u]) { if (bcc[v] || v == p && !pass) { pass = true; continue; } if (!low[v]) { dfs(v, u); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], num[v]); } if (low[u] == num[u]) { bcc[u] = ++cc; while (st.top() != u) { bcc[st.top()] = cc; st.pop(); } st.pop(); } } } int st[N], ed[N], it; int root[N], par[N]; bool mk[N], vst[N]; void dfs(int u, int p = - 1) { st[u] = ++it; root[u] = u; for (const auto& [v, way] : ad[u]) { if (v == p) continue; par[v] = u; mk[v] = way; dfs(v, u); } ed[u] = it; } bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; ++i) cin >> from[i] >> to[i]; cin >> p; for (int i = 1; i <= p; ++i) cin >> a[i] >> b[i]; for (int i = 1; i <= m; ++i) { int u = from[i], v = to[i]; BCC::ad[u].push_back(v); BCC::ad[v].push_back(u); } BCC::dfs(1); for (int i = 1; i <= m; ++i) { int u = BCC::bcc[from[i]], v = BCC::bcc[to[i]]; if (u == v) continue; ad[u].push_back({v, true}); ad[v].push_back({u, false}); } dfs(par[1] = 1); for (int i = 1; i <= p; ++i) { int u = BCC::bcc[a[i]], v = BCC::bcc[b[i]]; if (u == v) continue; { vector<int> vt; while (!anc(par[root[u]], v)) { vt.push_back(u); u = par[root[u]]; } vt.push_back(u); for (const auto& x : vt) { root[x] = u; mk[x] ^= 1; vst[x] = true; } } { vector<int> vt; while (!anc(par[root[v]], u)) { vt.push_back(v); v = par[root[v]]; } vt.push_back(v); for (const auto& x : vt) { vst[x] = true; root[x] = u; } } } for (int i = 1; i <= m; ++i) { int u = from[i], v = to[i]; int x = BCC::bcc[u], y = BCC::bcc[v]; if (x == y) cout << "B"; else if (anc(x, y)) cout << (!vst[y] ? 'B' : mk[y] ? 'R' : 'L'); else cout << (!vst[x] ? 'B' : mk[x] ? 'R' : 'L'); } }

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'void BCC::dfs(int, int)':
oneway.cpp:21:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   21 |       if (bcc[v] || v == p && !pass) {
      |                     ~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...