Submission #574057

#TimeUsernameProblemLanguageResultExecution timeMemory
574057MohammadAghilOne-Way Streets (CEOI17_oneway)C++14
100 / 100
211 ms26912 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 21, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} vector<int> adj[maxn]; int par[maxn], cnt[maxn]; vector<pp> his; int get(int x){ return par[x] == -1? x: get(par[x]); } bool unite(int u, int v){ u = get(u), v = get(v); if(u == v) return his.pb({-1, -1}), false; if(cnt[u] < cnt[v]) swap(u, v); par[v] = u, cnt[u] += cnt[v]; return his.pb({v, u}), true; } void undo(){ auto[v, u] = his.back(); his.pop_back(); if(u + 1) par[v] = -1, cnt[u] -= cnt[v]; } pp edge[maxn]; bool cut_edge[maxn], vis[maxn]; void slv(int l, int r){ if(l + 1 == r) { cut_edge[l] = get(edge[l].ff) != get(edge[l].ss); return; } int mid = (l + r)>>1; rep(i,mid,r) unite(edge[i].ff, edge[i].ss); slv(l, mid); rep(i,mid,r) undo(); rep(i,l,mid) unite(edge[i].ff, edge[i].ss); slv(mid, r); rep(i,l,mid) undo(); } vector<int> adj2[maxn]; int st[maxn]; map<pp, bool> is; void add_query(int u, int v){ st[u]++, st[v]--; } void dfs(int r, int p){ vis[r] = true; for(int c: adj2[r]) if(c - p){ dfs(c, r); st[r] += st[c]; } if(st[r]){ if(st[r] > 0) is[{r, p}] = true; else is[{p, r}] = true; } } int main(){ cin.tie(0) -> sync_with_stdio(0); int n, m; cin >> n >> m; fill(par, par + n, -1); fill(cnt, cnt + n, 1); rep(i,0,m){ cin >> edge[i].ff >> edge[i].ss; edge[i].ff--, edge[i].ss--; } slv(0, m); rep(i,0,m) if(!cut_edge[i]) unite(edge[i].ff, edge[i].ss); vector<int> grp(n, -1); int id = 0; rep(i,0,n){ if(grp[get(i)] == -1) grp[get(i)] = id++; grp[i] = grp[get(i)]; } rep(i,0,m) if(cut_edge[i]) { adj2[grp[edge[i].ff]].pb(grp[edge[i].ss]); adj2[grp[edge[i].ss]].pb(grp[edge[i].ff]); } int q; cin >> q; while(q--){ int u, v; cin >> u >> v; u = grp[--u], v = grp[--v]; add_query(u, v); } rep(i,0,n) if(!vis[i]) dfs(i, i); vector<int> ans(m); rep(i,0,m){ if(cut_edge[i]){ if(is.count({grp[edge[i].ff], grp[edge[i].ss]})) ans[i] = 1; else if(is.count({grp[edge[i].ss], grp[edge[i].ff]})) ans[i] = 2; } } for(int c: ans) cout << (c?(c&1?'R':'L'):'B'); return 0; }

Compilation message (stderr)

oneway.cpp: In function 'void undo()':
oneway.cpp:33:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |      auto[v, u] = his.back(); his.pop_back();
      |          ^
oneway.cpp: In function 'int main()':
oneway.cpp:95:38: warning: operation on 'u' may be undefined [-Wsequence-point]
   95 |           int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
oneway.cpp:95:52: warning: operation on 'v' may be undefined [-Wsequence-point]
   95 |           int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...