Submission #971459

#TimeUsernameProblemLanguageResultExecution timeMemory
971459efedmrlrOne-Way Streets (CEOI17_oneway)C++17
100 / 100
134 ms32036 KiB
#include <bits/stdc++.h> #define lli long long int #define ld long double #define pb push_back #define MP make_pair #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define REP(i, n) for(int i = 0; (i) < (n); (i)++) using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 1e5 + 5; const int INF = 1e9 + 500; const int LGN = 20; int n, m; vector<array<int, 2> > edg(N); vector<char> res(N, '$'); struct Bridge { vector<vector<array<int, 2> > > adj; vector<int> tin, low; vector<bool> vis; vector<bool> isBr; int tim = 0; int curc = 0; Bridge() { } void reset() { tin.assign(N, -1); low.assign(N, -1); vis.assign(N, 0); isBr.assign(N, 0); adj.assign(N, vector<array<int, 2> >()); tim = 0; } void dfs(int node, int pedg) { tin[node] = low[node] = tim++; vis[node] = 1; for(auto c : adj[node]) { if(c[1] == pedg) continue; if(vis[c[0]]) { low[node] = min(low[node], tin[c[0]]); } else { dfs(c[0], c[1]); low[node] = min(low[node], low[c[0]]); if(low[c[0]] > tin[node]) { //bridge found isBr[c[1]] = 1; } } } } void dfs2(int node, int par, vector<int> &comp) { for(auto c : adj[node]) { if(comp[c[0]] != -1 || isBr[c[1]]) { continue; } comp[c[0]] = comp[node]; dfs2(c[0], node, comp); } } void find_comp(vector<int> &comp) { curc = 0; comp.assign(n + 1, -1); for(int i = 1; i <= n; i++) { if(comp[i] != -1) continue; comp[i] = curc++; dfs2(i, i, comp); } } }; struct Tre { vector<vector<array<int, 2> > > adj; vector<int> head; vector<int> subt, dep; vector<int> p, pedg; vector<int> dir; int n; Tre() { adj.assign(N, vector<array<int, 2> >()); subt.assign(N, -1); dep.assign(N, 0); p.assign(N, 0); head.assign(N, 0); pedg.assign(N, m); dir.assign(N, 0); } void dfssz(int node) { subt[node] = 1; for(auto &c : adj[node]) { p[c[0]] = node; pedg[c[0]] = c[1]; adj[c[0]].erase(find(all(adj[c[0]]), array<int,2>({node, c[1]}))); dfssz(c[0]); subt[node] += subt[c[0]]; if(subt[adj[node][0][0]] < subt[c[0]]) { swap(adj[node][0], c); } } } void dfshld(int node) { for(auto c : adj[node]) { head[c[0]] = (c == adj[node][0]) ? head[node] : c[0]; dep[c[0]] = dep[node] + 1; dfshld(c[0]); } } int lca(int x, int y) { while(head[x] != head[y]) { if(dep[head[x]] < dep[head[y]]) swap(x, y); x = p[head[x]]; } if(dep[x] < dep[y]) { swap(x, y); } return y; } void init(int curc) { n = curc; for(int i = 0; i < n; i++) { p[i] = i; } for(int i = 0; i < n; i++) { if(subt[i] != -1) continue; dep[i] = 0; dfssz(i); head[i] = i; dfshld(i); } } void mark(int x, bool b) { if(b) { dir[x] = 2; } else { dir[x] = 1; } } }; void solve() { cin >> n >> m; for(int i = 0; i < m; i++) { cin >> edg[i][0] >> edg[i][1]; } Bridge br; br.reset(); for(int i = 0; i < m; i++) { br.adj[edg[i][0]].pb({edg[i][1], i}); br.adj[edg[i][1]].pb({edg[i][0], i}); } for(int i = 1; i<=n; i++) { if(br.vis[i]) continue; br.dfs(i, m); } vector<int> cmp; br.find_comp(cmp); // for(int i = 0; i < m; i++) { // if(br.isBr[i]) { // cout << "i:" << i << " a:" << edg[i][0] << " b:" << edg[i][1] << "\n"; // } // } // for(int i = 1; i <= n; i++) { // cout << "i: " << i << " " << cmp[i] << " "; // } // cout << endl; Tre t; for(int i = 0; i < m; i++) { if(!br.isBr[i]) { // cout << "not bridge:" << i << "\n"; res[i] = 'B'; } else { edg[i] = {cmp[edg[i][0]], cmp[edg[i][1]]}; t.adj[edg[i][0]].pb({edg[i][1], i}); t.adj[edg[i][1]].pb({edg[i][0], i}); // cout << edg[i][0] << " edg" << edg[i][1] << "\n"; } } // cout << br.curc << " curc\n" << endl; t.init(br.curc); // for(int i = 0; i < br.curc; i++) { // cout << "i:" << i <<" p:" << t.p[i] << "pedg:" << t.pedg [i] << endl; // } int p; cin >> p; vector<array<int, 3> > tmp; REP(i, p) { int x, y; cin >> x >> y; x = cmp[x]; y = cmp[y]; if(x == y) continue; int lc = t.lca(x, y); tmp.pb({t.dep[lc], x, 0}); tmp.pb({t.dep[lc], y, 1}); } sort(all(tmp)); for(auto c : tmp) { int x = c[1]; while(t.dep[x] > c[0] && t.dir[x] == 0) { t.mark(x, c[2]); x = t.p[x]; } } for(int i = 0; i < t.n; i++) { if(t.p[i] == i) continue; int cur = t.pedg[i]; if(t.dir[i] == 0) { res[cur] = 'B'; continue; } if(edg[cur][0] == i) { if(t.dir[i] == 1) { res[cur] = 'R'; } else { res[cur] = 'L'; } } else { if(t.dir[i] == 1) { res[cur] = 'L'; } else { res[cur] = 'R'; } } } for(int i = 0; i < m; i++) { cout << res[i]; } cout << "\n"; } signed main() { fastio(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...