Submission #1191630

#TimeUsernameProblemLanguageResultExecution timeMemory
1191630loomOne-Way Streets (CEOI17_oneway)C++20
0 / 100
2 ms3648 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define inf 5e18 #define nl '\n' const int N = 1e5+1; int dep[N], up[N][17], ix[N], op[N], vis[N], tin[N], low[N]; vector<tuple<int,int,int>> g[N]; char ans[N]; int cnt; void dfs1(int v){ vis[v] = 1; for(auto [ch, i, t] : g[v]){ if(vis[ch]) continue; dep[ch] = dep[v]+1; up[ch][0] = v; ix[ch] = i; op[ch] = t; dfs1(ch); } } void dfs2(int v, int pe){ vis[v] = 1; tin[v] = low[v] = cnt++; for(auto [ch, i, t] : g[v]){ if(i == pe) continue; if(vis[ch]){ low[v] = min(low[v], tin[ch]); ans[i] = 'B'; continue; } dfs2(ch, i); low[v] = min(low[v], low[ch]); if(low[ch] <= tin[v]) ans[i] = 'B'; } } int lca(int x, int y){ if(dep[x] > dep[y]) swap(x, y); int k = dep[y] - dep[x]; for(int i=0; i<17; i++){ if(k & (1<<i)) y = up[y][i]; } if(x == y) return x; for(int i=16; i>=0; i--){ if(up[x][i] != up[y][i]){ x = up[x][i]; y = up[y][i]; } } return up[x][0]; } inline void solve(){ int n, m; cin>>n>>m; for(int i=0; i<m; i++){ int a, b; cin>>a>>b; if(a == b){ ans[i] = 'B'; continue; } g[a].push_back({b, i, 1}); g[b].push_back({a, i, 0}); } dfs1(1); for(int j=1; j<17; j++){ for(int i=1; i<=n; i++){ up[i][j] = up[up[i][j-1]][j-1]; } } fill(ans, ans+N, ' '); int p; cin>>p; vector<tuple<int,int,int>> v; for(int i=0; i<p; i++){ int x, y; cin>>x>>y; int l = lca(x, y); v.push_back({dep[l], x, y}); } sort(v.begin(), v.end()); for(auto [d, x, y] : v){ int l = lca(x, y); while(x != l){ if(ans[ix[x]] != ' ') break; ans[ix[x]] = (op[x] ? 'L' : 'R'); x = up[x][0]; } while(y != l){ if(ans[ix[y]] != ' ') break; ans[ix[y]] = (op[y] ? 'R' : 'L'); y = up[y][0]; } } fill(vis, vis+N, 0); dfs2(1, -1); for(int i=0; i<m; i++) cout<<ans[i]; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...