Submission #237818

#TimeUsernameProblemLanguageResultExecution timeMemory
237818NucleistOne-Way Streets (CEOI17_oneway)C++14
100 / 100
814 ms83940 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll long long #define INF 1000000000 #define MOD 1000000007 #define pb push_back #define ve vector<ll> #define dos pair<ll,ll> #define vedos vector<dos> #define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define EPS 0.000001 struct greateri { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } ll tin[200001],tlow[200001],vis[200001],vis1[200001],dep[200001],pa[200001][30]; ve gr[200001],gr1[200001],tr[200001]; set<dos>brid; ll n,m,p; char ans[200001]; map<dos,ve>g; ll timer,l; ll col[200001]; void dfs(ll node,ll p){ vis[node]=1; tin[node]=timer++; tlow[node]=tin[node]; for(auto it:gr[node]){ if(it==p || it==node)continue; if(vis[it]){ tlow[node]=min(tin[it],tlow[node]); } else{ dfs(it,node); tlow[node]=min(tlow[node],tlow[it]); if(tlow[it]>tin[node]){ brid.insert({min(node,it),max(node,it)}); } } } } void dfs1(ll node,ll co){ col[node]=co; vis1[node]=1; for(auto it:gr1[node]){ if(!vis1[it]){ dfs1(it,co); } } } void dfk(ll node,ll p,ll ka){ vis1[node]=1; tin[node]=timer++; dep[node]=ka; pa[node][0]=p; for (ll i = 1; i <= l; ++i) { pa[node][i]=pa[pa[node][i-1]][i-1]; } for(auto it:tr[node]){ if(it!=p){ dfk(it,node,ka+1); } } tlow[node]=timer++; } bool is_anc(ll u,ll v){ if(tin[u]<=tin[v] && tlow[u]>=tlow[v])return 1; return 0; } ll lca(ll u,ll v){ if(is_anc(u,v))return u; if(is_anc(v,u))return v; for (ll i = l; i >= 0; --i) { if(!is_anc(pa[u][i],v)){ u=pa[u][i]; } } return pa[u][0]; } ll parent[200000], depth[200000], heavy[200000], head[200000], pos[200000]; ll cur_pos; ll lom(ll v) { vis1[v]=1; ll size = 1; ll max_c_size = 0; for (ll c : tr[v]) { if (c != parent[v]) { parent[c] = v, depth[c] = depth[v] + 1; ll c_size = lom(c); size += c_size; if (c_size > max_c_size) max_c_size = c_size, heavy[v] = c; } } return size; } ll decompose(ll v, ll h) { head[v] = h, pos[v] = cur_pos++; if (heavy[v] != -1) decompose(heavy[v], h); for (ll c : tr[v]) { if (c != parent[v] && c != heavy[v]) decompose(c, c); } } ll bit[200001]; void add(ll idx, ll val) { for (idx; idx <= n; idx += idx & -idx) bit[idx] += val; } void range_add(ll l, ll r, ll val) { add(l, val); add(r + 1, -val); } ll point_query(ll idx) { ll ret = 0; for (idx; idx > 0; idx -= idx & -idx) ret += bit[idx]; return ret; } void query(ll a, ll b,ll val) { ll res = 0; for (; head[a] != head[b]; b = parent[head[b]]) { if (depth[head[a]] > depth[head[b]]) swap(a, b); //debugs(pos[head[b]],pos[b]) //debug(val) range_add(pos[head[b]]+1, pos[b]+1,val); //debug(point_query(pos[head[b]]+1)) //res = max(res, cur_heavy_path_max); } if (depth[a] > depth[b]) swap(a, b); //debugs(a,b) //debug(val) range_add(pos[a]+1, pos[b]+1,val); return; } int main() { //flash; cin>>n>>m; l=log2(n); vedos ed; for (ll i = 0; i < m; ++i) { ll u,v; cin>>u>>v; u--,v--; if(u==v){ ans[i]='B'; } else{ ed.pb({u,v}); gr[u].pb(v),gr[v].pb(u); if(u>v)swap(u,v); g[{u,v}].pb(i); } } for(auto it:g){ if(it.second.size()>1){ for(auto it1:it.second){ ans[it1]='B'; } } } for (int i = 0; i < n; ++i) { if(!vis[i])dfs(i,-1); } set<dos>rem; for(auto it:brid){ if(g[{it.first,it.second}].size()>1)rem.insert(it); } for(auto it:rem)brid.erase(it); for(auto it:ed){ auto u=it.first,v=it.second; if(u>v)swap(u,v); if(brid.find({u,v})==brid.end()){ gr1[u].pb(v),gr1[v].pb(u); } } ll ci=1; for (ll i = 0; i < n; ++i) { if(!vis1[i]){ dfs1(i,ci); ci++; } } timer=0; for(auto it:brid){ tr[col[it.first]].pb(col[it.second]); tr[col[it.second]].pb(col[it.first]); } memset(vis1,0,sizeof vis1); for (int i = 1; i < ci; ++i) { if(!vis1[i]){timer=0,dfk(i,i,0);} } ll q; cin>>q; memset(heavy,-1,sizeof heavy); memset(vis1,0,sizeof vis1); for (int i = 1; i < ci; ++i) { if(!vis1[i]){lom(i),decompose(i,i);} } while(q--){ ll u,v; cin>>u>>v; u--,v--; if(col[u]==col[v])continue; ll dol=lca(col[u],col[v]); query(col[u],dol,1); query(col[v],dol,-1); } for (ll i = 0; i < ed.size(); ++i) { auto u=ed[i].first,v=ed[i].second; if(u>v)swap(u,v); if(ans[i]!='B' && brid.find({u,v})!=brid.end() && col[u]!=col[v]){ if(dep[col[u]]<=dep[col[v]])swap(u,v); ll cur=point_query(pos[col[u]]+1); if(cur>0){ if(ed[i].first==u)ans[i]='R'; else ans[i]='L'; } else if(cur<0){ if(ed[i].first==u)ans[i]='L'; else ans[i]='R'; } else ans[i]='B'; } else ans[i]='B'; } for (ll i = 0; i < m; ++i) { cout<<ans[i]; } return 0; } //code the AC sol ! // BS/queue/map

Compilation message (stderr)

oneway.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
oneway.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
oneway.cpp: In function 'long long int decompose(long long int, long long int)':
oneway.cpp:122:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
oneway.cpp: In function 'void add(long long int, long long int)':
oneway.cpp:125:13: warning: statement has no effect [-Wunused-value]
     for (idx; idx <= n; idx += idx & -idx)
             ^
oneway.cpp: In function 'long long int point_query(long long int)':
oneway.cpp:136:13: warning: statement has no effect [-Wunused-value]
     for (idx; idx > 0; idx -= idx & -idx)
             ^
oneway.cpp: In function 'void query(long long int, long long int, long long int)':
oneway.cpp:141:8: warning: unused variable 'res' [-Wunused-variable]
     ll res = 0;
        ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:237:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (ll i = 0; i < ed.size(); ++i)
                  ~~^~~~~~~~~~~
oneway.cpp: In function 'void setIO(std::__cxx11::string)':
oneway.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".in").c_str(),"r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".out").c_str(),"w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...