Submission #894820

#TimeUsernameProblemLanguageResultExecution timeMemory
894820Sir_Ahmed_ImranFountain Parks (IOI21_parks)C++17
30 / 100
492 ms56648 KiB
///~~~LOTA~~~/// #include "parks.h" #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define N 200001 int siz[N]; int par[N]; int root(int v){ if(!par[v]) return v; par[v]=root(par[v]); return par[v]; } void merge(int v,int u){ v=root(v); u=root(u); par[u]=v; siz[v]+=siz[u]; } bool same(int v,int u){ return (root(v)==root(u)); } int construct_roads(vector<int> x,vector<int> y){ map<pii,int> c,z; int n,m,o,p,q,r; n=x.size(); vector<int> v,u,a,b; vector<pair<pii,int>> w; for(int i=0;i<n;i++){ w.append({{y[i],x[i]},i+1}); z[{x[i],y[i]}]=i+1; siz[i+1]=1; } sort(all(w)); for(auto& i:w){ q=i.ff.ff; p=i.ff.ss; r=z[{p-2,q}]; if(r){ if(!same(i.ss,r)){ merge(i.ss,r); v.append(i.ss-1); u.append(r-1); if(!c[{p-1,q-1}]){ a.append(p-1); b.append(q-1); c[{p-1,q-1}]=1; } else if(!c[{p-1,q+1}]){ a.append(p-1); b.append(q+1); c[{p-1,q+1}]=1; } else return 0; } } r=z[{p,q-2}]; if(r){ if(!same(i.ss,r)){ merge(i.ss,r); v.append(i.ss-1); u.append(r-1); if(!c[{p-1,q-1}]){ a.append(p-1); b.append(q-1); c[{p-1,q-1}]=1; } else if(!c[{p+1,q-1}]){ a.append(p+1); b.append(q-1); c[{p+1,q-1}]=1; } else return 0; } } } if(siz[root(1)]!=n) return 0; build(u,v,a,b); return 1; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:31:11: warning: unused variable 'm' [-Wunused-variable]
   31 |     int n,m,o,p,q,r;
      |           ^
parks.cpp:31:13: warning: unused variable 'o' [-Wunused-variable]
   31 |     int n,m,o,p,q,r;
      |             ^
#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...