Submission #1020337

#TimeUsernameProblemLanguageResultExecution timeMemory
1020337idiotcomputerOne-Way Streets (CEOI17_oneway)C++11
0 / 100
5 ms12380 KiB
#include <bits/stdc++.h> using namespace std; #define sz size #define pb push_back #define pii pair<int,int> #define f first #define s second const int mxN = 1e5+5; int vis[mxN]; vector<pii> adj[mxN]; int d[mxN]; int low[mxN]; char res[mxN]; set<int> st[mxN]; set<int> en[mxN]; int p[mxN]; int gpar(int a){ if (p[a] == a) return a; p[a] = gpar(p[a]); return p[a]; } void dfs(int c, int depth, int pidx){ d[c] = depth; low[c] = depth; p[c] = c; for (pii i : adj[c]){ if (vis[abs(i.s)]) continue; vis[abs(i.s)] = 1; if (d[i.f] != -1){ low[c] = min(low[c],low[i.f]); res[abs(i.s)] = 'B'; continue;} dfs(i.f,depth+1,i.s); low[c] = min(low[c],low[i.f]); } int a,b; for (pii i : adj[c]){ if (d[i.f] < d[c]) continue; a = c; b = i.f; a = gpar(a); b = gpar(b); if ((int) st[a].sz() + (int) en[a].sz() < (int) st[b].sz() + (int) en[b].sz()) swap(a,b); for (int i : st[b]){ if (en[a].find(i) != en[a].end()) en[a].erase(i); else st[a].insert(i); } for (int i : en[b]){ if (st[a].find(i) != st[a].end()) st[a].erase(i); else en[a].insert(i); } p[b] = a; } if (pidx == INT_MAX) return; // cout << c << " " << low[c] << " " << d[c] << "\n"; if (low[c] < d[c]) res[pidx] = 'B'; else { a = gpar(c); if (st[a].sz() == 0 && en[a].sz() == 0) res[pidx] = 'B'; else if (st[a].sz() == 0) { if (pidx > 0) res[abs(pidx)] = 'R'; else res[abs(pidx)] = 'L'; } else { if (pidx > 0) res[abs(pidx)] = 'L'; else res[abs(pidx)] = 'R'; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; int a,b; for (int i =0; i < m; i++){ cin >> a >> b; a -= 1; b -= 1; adj[a].pb((pii) {b,i+1}); adj[b].pb((pii) {a,-1*i-1}); } int p; cin >> p; for (int i =0; i < p; i++){ cin >> a >> b; a -= 1; b -= 1; st[a].insert(i); en[b].insert(i); } memset(vis,0,sizeof(vis)); for (int i = 0; i < n; i++) d[i] = -1; for (int i = 0; i < n; i++) if (d[i] == -1) dfs(i,0,INT_MAX); for (int i = 1; i <= m; i++) cout << res[i]; cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...