Submission #986959

#TimeUsernameProblemLanguageResultExecution timeMemory
986959AverageAmogusEnjoyerOne-Way Streets (CEOI17_oneway)C++17
60 / 100
3021 ms17712 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i,T j) { return i > j ? i = j,true: false; } template<class T> bool cmax(T &i,T j) { return i < j ? i = j,true: false; } struct RMQ { int n; int lg; vector<vector<int>> sparse; RMQ() {} RMQ(vector<int> a) { if (a.empty()) { return; } n = (int)a.size(); lg = 0; while((1<<lg) <= n) { lg++; } sparse.assign(lg,vector<int>(n)); sparse[0] = a; for (int pw=1;pw<lg;pw++) { for (int i=0;i<n;i++) { sparse[pw][i] = min(sparse[pw-1][i],sparse[pw-1][min(i+(1<<(pw-1)),n-1)]); } } } int qry(int l,int r) { assert(0 <= l && l <= r && r < n); int bit = 31-__builtin_clz(r-l+1); return min(sparse[bit][l],sparse[bit][r-(1<<bit)+1]); } }; struct LCA { int n; vector<vector<pair<int,int>>> adj; vector<int> tin,path,ret; RMQ rmq; int timer = 0; LCA(int N,vector<vector<pair<int,int>>> a) { adj = a; n = N; tin.resize(n); dfs(); rmq = RMQ(ret); } void dfs(int x=0,int z=-1) { tin[x] = timer++; for (auto &[y,idx]: adj[x]) if (y != z) { path.push_back(x),ret.push_back(tin[x]); dfs(y,x); } } int lca(int x,int y) { if (x == y) { return x; } if (tin[x] > tin[y]) { swap(x,y); } return path[rmq.qry(tin[x],tin[y]-1)]; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; string ans(m,'B'); vector<vector<pair<int,int>>> adj(n); vector<pair<int,int>> edges(m); for (int i=0,x,y;i<m;i++) { cin >> x >> y; --x,--y; edges[i] = make_pair(x,y); adj[x].emplace_back(y,i); adj[y].emplace_back(x,i); } vector<vector<pair<int,int>>> tree(n); // vector<vector<pair<int,int>>> back_edges(n); vector<int> dp(n); vector<int> t(n,-1); int timer = 0; vector<bool> vst(n); vector<int> par(n); auto dfs = [&](auto &self,int x,int z) -> void { t[x] = timer++; vst[x]=true; par[x]=z; for (auto &[y,idx]: adj[x]) if (y != z) { if (t[y] > t[x]) { // back_edges[y].emplace_back(x,idx); // cout << "back edge: " << y+1 << " " << x+1 << endl; dp[y]++; dp[x]--; } else if (t[y] == -1) { tree[x].emplace_back(y,idx); // cout << "span edge: " << x+1 << " " << y+1 << endl; self(self,y,x); } } }; vst.assign(n,false); for (int x=0;x<n;x++) if (!vst[x]) { dfs(dfs,x,-1); } auto dfstree = [&](auto &self,int x,int z) -> void { vst[x]=true; for (auto &[y,idx]: tree[x]) if (y != z) { self(self,y,x); dp[x] += dp[y]; } }; vst.assign(n,false); for (int x=0;x<n;x++) if (!vst[x]) { dfstree(dfstree,x,-1); } vector<int> up(n),down(n); // LCA tr(n,tree); int q; cin >> q; for (int x,y;q--;) { cin >> x >> y; --x,--y; // int l = tr.lca(x,y); vst.assign(n,false); int cx = x; while(cx != -1) { vst[cx] = true; cx = par[cx]; } int cy = y; while(!vst[cy]) { cy = par[cy]; assert(cy != -1); } int l = cy; up[x]++; up[l]--; down[y]++; down[l]--; } auto dfspush = [&](auto &self,int x,int z) -> void { vst[x]=true; for (auto &[y,idx]: tree[x]) if (y != z) { self(self,y,x); up[x] += up[y]; down[x] += down[y]; // actually write down edge if (dp[y] != 0) { continue; } assert(up[y] == 0 || down[y] == 0); if (up[y]) { if (edges[idx].second == x) { ans[idx] = 'R'; } else { ans[idx] = 'L'; } } else if (down[y]) { if (edges[idx].second == y) { ans[idx] = 'R'; } else { ans[idx] = 'L'; } } } }; vst.assign(n,false); for (int x=0;x<n;x++) if (!vst[x]) { dfspush(dfspush,x,-1); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...