제출 #563696

#제출 시각아이디문제언어결과실행 시간메모리
563696hohohahaOne-Way Streets (CEOI17_oneway)C++14
100 / 100
217 ms46312 KiB
#include<bits/stdc++.h> using namespace std; #define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) #define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) #define ii pair<int, int> #define fi first #define se second #define vi vector<int> #define eb emplace_back #define em emplace #define sp ' ' #define endl '\n' //#define int long long #define ld long double const int maxn = 2e5 + 5; int n, m; vector<pair<int, ii> > g[maxn]; ii E[maxn]; int tin[maxn]; int tinpt; int low[maxn]; bool bridge[maxn]; stack<int> st; int cc[maxn]; int q; int x[maxn]; int y[maxn]; vector<pair<int, ii> > g2[maxn]; int tout[maxn]; int dep[maxn]; int par[maxn][20]; int parid[maxn]; int pardir[maxn]; int dir[maxn][20]; int ans[maxn]; void dfs_prep(int u, int pid) { tin[u] = low[u] = ++tinpt; st.push(u); for(auto e: g[u]) { int v = e.fi, id = e.se.fi, dir = e.se.se; if(id == pid) continue; if(!tin[v]) { dfs_prep(v, id); low[u] = min(low[u], low[v]); } else if(tin[v] < tin[u]) { low[u] = min(low[u], tin[v]); } } if(low[u] >= tin[u]) { while(1) { int top = st.top(); cc[top] = u; st.pop(); if(top == u) break; } if(pid >= 0) bridge[pid] = 1; } } void dfs_prep_2(int u, int p) { tin[u] = ++tinpt; fori(bit, 1, 19) { par[u][bit] = par[par[u][bit - 1]][bit - 1]; } for(auto e: g2[u]) { int v = e.fi, id = e.se.fi, dir = e.se.se; if(v - p) { dep[v] = dep[u] + 1; par[v][0] = u; parid[v] = id; pardir[v] = dir ^ 1; dfs_prep_2(v, u); } } tout[u] = tinpt; } bool isan(int u, int v) { return tin[u] <= tin[v] and tout[v] <= tout[u]; } void jump(int u, int v, int dir) { if(isan(u, v)) return; //cout << "jump " << u << v << endl; ford(bit, 19, 0) { if(isan(par[u][bit], v)) continue; ::dir[u][bit] = dir; u = par[u][bit]; } ::dir[u][0] = dir; // cout << "lca: " << par[u][0] << endl; } signed main() { // freopen("oneway.inp", "r", stdin); // freopen("oneway.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; fori(i, 1, m) { int u, v; cin >> u >> v; E[i] = ii(u, v); g[u].eb(make_pair(v, ii(i, 0))); g[v].eb(make_pair(u, ii(i, 1))); } fori(i, 1, n) if(!tin[i]) dfs_prep(i, -1); //fori(i, 1, n) cout << cc[i] << endl; fori(i, 1, m) if(bridge[i]) g2[cc[E[i].fi]].eb(make_pair(cc[E[i].se], ii(i, 0))), g2[cc[E[i].se]].eb(make_pair(cc[E[i].fi], ii(i, 1))); // tinpt = 0; fill(tin + 1, tin + n + 1, 0ll); fori(i, 1, n) if(!tin[i]) { par[i][0] = i; dfs_prep_2(i, i); } cin >> q; fori(i, 1, q) { cin >> x[i] >> y[i]; if(cc[x[i]] == cc[y[i]]) continue; jump(cc[x[i]], cc[y[i]], 1); jump(cc[y[i]], cc[x[i]], 2); } ford(bit, 19, 1) { fori(i, 1, n) { if(dir[i][bit]) { dir[i][bit - 1] = dir[i][bit]; dir[par[i][bit - 1]][bit - 1] = dir[i][bit]; } } } fori(i, 1, n) { if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1; } fori(i, 1, m) { if(ans[i] == 1) cout << "R"; else if(ans[i] == 2) cout << "L"; else cout << "B"; } }

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

oneway.cpp: In function 'void dfs_prep(int, int)':
oneway.cpp:49:31: warning: unused variable 'dir' [-Wunused-variable]
   49 |   int v = e.fi, id = e.se.fi, dir = e.se.se;
      |                               ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:77: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  152 |     if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1;
      |                                                                   ~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...