Submission #796301

#TimeUsernameProblemLanguageResultExecution timeMemory
796301KhizriFountain Parks (IOI21_parks)C++17
0 / 100
1 ms212 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) const int mxn=2e5+5; int n,x[mxn],y[mxn],p[mxn],sz[mxn]; int ax[4]={1,1,-1,-1}; int ay[4]={-1,1,1,-1}; vector<pii>vt; map<pii,int>mp; int fnd(int u){ if(p[u]==u) return u; return p[u]=fnd(p[u]); } void Union(int u,int v){ u=fnd(u); v=fnd(v); if(u!=v){ if(sz[u]>sz[v]) swap(u,v); sz[u]+=sz[v]; p[v]=u; } } bool cmp(pii a,pii b){ return a.F+a.S<b.F+b.S; } int construct_roads(vector<int> xx, vector<int> yy) { n=xx.size(); if(n==1){ build({},{},{},{}); return 1; } for(int i=0;i<n;i++){ vt.pb({xx[i],yy[i]}); mp[{xx[i],yy[i]}]=i+1; x[i+1]=xx[i]; y[i+1]=yy[i]; } set<pii>st; for(int i=1;i<=n;i++){ p[i]=i; sz[i]=1; } vector<int>idxl,idxr,posl,posr; sort(all(vt),cmp); for(int i=1;i<n;i++){ int l=vt[i].F,r=vt[i].S; int a=l-2,b=r; int c=l,d=r-2; int u=mp[{l,r}]; int idx=mp[{a,b}]; int idx2=mp[{c,d}]; if(!idx&&!idx2){ return 0; } if(idx&&idx2){ int p1=(a+l)/2,p2=(b+r)/2; if(p1%2){ if(!st.count({p1,p2-1})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1); posr.pb(p2-1); st.insert({p1,p2-1}); continue; } else if(!st.count({p1,p2+1})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1); posr.pb(p2+1); st.insert({p1,p2+1}); continue; } } else{ if(!st.count({p1-1,p2})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1-1); posr.pb(p2); st.insert({p1-1,p2}); continue; } else if(!st.count({p1+1,p2})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1+1); posr.pb(p2); st.insert({p1+1,p2}); continue; } } p1=(c+l)/2,p2=(d+r)/2; if(p1%2){ if(!st.count({p1,p2-1})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1); posr.pb(p2-1); st.insert({p1,p2-1}); continue; } else if(!st.count({p1,p2+1})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1); posr.pb(p2+1); st.insert({p1,p2+1}); continue; } } else{ if(!st.count({p1-1,p2})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1-1); posr.pb(p2); st.insert({p1-1,p2}); continue; } else if(!st.count({p1+1,p2})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1+1); posr.pb(p2); st.insert({p1+1,p2}); continue; } } } else if(idx){ int p1=(a+l)/2,p2=(b+r)/2; if(p1%2){ if(!st.count({p1,p2-1})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1); posr.pb(p2-1); st.insert({p1,p2-1}); continue; } else if(!st.count({p1,p2+1})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1); posr.pb(p2+1); st.insert({p1,p2+1}); continue; } } else{ if(!st.count({p1-1,p2})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1-1); posr.pb(p2); st.insert({p1-1,p2}); continue; } else if(!st.count({p1+1,p2})){ idxl.pb(u); idxr.pb(idx); posl.pb(p1+1); posr.pb(p2); st.insert({p1+1,p2}); continue; } } } else if(idx2){ int p1=(c+l)/2,p2=(d+r)/2; if(p1%2){ if(!st.count({p1,p2-1})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1); posr.pb(p2-1); st.insert({p1,p2-1}); continue; } else if(!st.count({p1,p2+1})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1); posr.pb(p2+1); st.insert({p1,p2+1}); continue; } } else{ if(!st.count({p1-1,p2})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1-1); posr.pb(p2); st.insert({p1-1,p2}); continue; } else if(!st.count({p1+1,p2})){ idxl.pb(u); idxr.pb(idx2); posl.pb(p1+1); posr.pb(p2); st.insert({p1+1,p2}); continue; } } } } build(idxl,idxr,posl,posr); return 1; } /* cd "c:\Users\User\Desktop\parks (4)\cpp\" ; if ($?) { g++ parks.cpp grader.cpp -o parks } ; if ($?) { .\a.exe } 5 4 4 4 6 6 4 4 2 2 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...