(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #1118829

#제출 시각아이디문제언어결과실행 시간메모리
1118829gdragonOne-Way Streets (CEOI17_oneway)C++17
0 / 100
6 ms6224 KiB
#include <bits/stdc++.h> using namespace std; #define TASK "long" #define fi first #define se second #define ll long long #define pb push_back #define ALL(x) (x).begin(), (x).end() #define GETBIT(mask, i) ((mask) >> (i) & 1) #define MASK(i) ((1LL) << (i)) #define SZ(x) ((int)(x).size()) #define mp make_pair #define CNTBIT(mask) __builtin_popcount(mask) template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;}; template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;}; typedef pair<int, int> ii; const int N = 1e5 + 5; const int inf = 1e9 + 7; const long long INF = (long long)1e18 + 7; const int mod = 1e9 + 7; struct Edge { int u, v; bool isBridge, used; Edge(int _u = 0, int _v = 0) { u = _u; v = _v; isBridge = used = 0; } } e[N]; int n, m, q; int low[N], num[N]; vector<int> adj[N]; vector<ii> newAdj[N]; void read() { cin >> n >> m; for(int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[i] = Edge(u, v); adj[u].push_back(i); adj[v].push_back(i); } } int timer = 0, cycle = 0; stack<int> st; int id[N]; void tarjan(int u) { low[u] = num[u] = ++timer; st.push(u); for(int i: adj[u]) if (!e[i].used) { e[i].used = 1; int v = e[i].u ^ e[i].v ^ u; if (num[v]) low[u] = min(low[u], num[v]); else { tarjan(v); low[u] = min(low[u], low[v]); } if (low[v] > num[u]) { // cerr << "BRIDGE: " << e[i].u << ' ' << e[i].v << endl; e[i].isBridge = 1; } } if (low[u] == num[u]) { ++cycle; // cerr << cycle << endl; while(true) { int v = st.top(); st.pop(); // cerr << v << ' '; low[v] = num[v] = inf; id[v] = cycle; if (v == u) break; } // cerr << endl; } } int tin[N], tout[N], high[N]; ii par[N]; bool isChild(int u, int p) { return tin[u] >= tin[p] && tin[u] <= tout[p]; } int jump[N]; void dfs(int u, int p) { // cerr << u << endl; tin[u] = ++timer; jump[u] = u; for(auto [v, i]: newAdj[u]) if (v != p) { par[v] = {u, i}; high[v] = high[u] + 1; dfs(v, u); } tout[u] = timer; } int ans[N]; int change[N]; vector<int> node; void solve() { tarjan(1); for(int i = 1; i <= m; i++) if (e[i].isBridge) { int u = id[e[i].u], v = id[e[i].v]; newAdj[u].push_back({v, i}); newAdj[v].push_back({u, i}); } timer = 0; dfs(1, -1); cin >> q; while(q--) { int u, v; cin >> u >> v; // cerr << id[u] << ' ' << id[v] << endl; if (id[u] == id[v]) continue; u = id[u]; v = id[v]; int tmp = u; // cerr << jump[u] << ' ' << v << ' ' << isChild(jump[u], v) << endl; while(!isChild(v, u)) { int i = par[u].se; // u = par[u].fi; ans[i] = 1; // node.push_back(u); u = par[u].fi; } // for(int x: node) jump[x] = u; node.clear(); u = tmp; while(!isChild(u, v)) { int i = par[v].se; ans[i] = 2; // cerr << v << ' ' << e[i].u << ' ' << e[i].v << endl; // node.push_back(v); v = par[v].fi; } // for(int x: node) jump[x] = v; node.clear(); } for(int i = 1; i <= m; i++) { // cout << e[i].u << ' ' << e[i].v << ' '; if (e[i].isBridge) { if (ans[i] != 0) { int u = e[i].u, v = e[i].v; if (high[id[u]] < high[id[v]]) { assert(isChild(id[v], id[u])); if (ans[i] == 2) cout << 'R'; else cout << 'L'; } else { assert(isChild(id[u], id[v])); if (ans[i] == 2) cout << 'L'; else cout << 'R'; } } else cout << 'B'; // cout << endl; continue; } else cout << 'B'; // cout << endl; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } int test = 1; // cin >> test; while(test--) { read(); solve(); } return 0; } // rmq - rmq2d // hash // fw - fw2d // segtree

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

oneway.cpp: In function 'int main()':
oneway.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...