Submission #436613

#TimeUsernameProblemLanguageResultExecution timeMemory
436613dqhungdlFountain Parks (IOI21_parks)C++17
30 / 100
829 ms49800 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; const int MAX=2e5+5; int n,P[MAX]; vector<int> x,y; map<ii,int> M; bool isVertical(ii u) { return x[u.first]==x[u.second]; } bool cmp(ii u,ii v) { if(x[u.first]==x[v.first]) { if(isVertical(u)==isVertical(v)) return y[u.first]<y[v.first]; return isVertical(u)>isVertical(v); } return x[u.first]<x[v.first]; } vector<ii> constructBenches(vector<ii> &paths) { map<ii,bool> mark,under; vector<ii> benchesPos; for(int i=0;i<paths.size();i++) { ii path=paths[i]; if(x[path.first]==x[path.second]) { int bx=x[path.first],by=y[path.first]+1; benchesPos.push_back({bx-1,by}); benchesPos.push_back({bx+1,by}); under[ii(bx-1,by)]=true; } else { int bx=x[path.first]+1,by=y[path.first]; benchesPos.push_back({bx,by-1}); benchesPos.push_back({bx,by+1}); } } vector<ii> benches; if(*max_element(x.begin(),x.end())<=6) { for(int i=0;i<paths.size();i++) { if(!mark[benchesPos[2*i]]) { mark[benchesPos[2*i]]=true; benches.push_back(benchesPos[2*i]); } else { mark[benchesPos[2*i+1]]=true; benches.push_back(benchesPos[2*i+1]); } } } else { for(int i=0;i<paths.size();i++) { ii path=paths[i]; if(x[path.first]==x[path.second]) { // Vertical if(!mark[benchesPos[2*i]]) { mark[benchesPos[2*i]]=true; benches.push_back(benchesPos[2*i]); } else { mark[benchesPos[2*i+1]]=true; benches.push_back(benchesPos[2*i+1]); } } else { // Horizontal if(mark[benchesPos[2*i]]||(under[benchesPos[2*i]]&&!under[benchesPos[2*i+1]])) { mark[benchesPos[2*i+1]]=true; benches.push_back(benchesPos[2*i+1]); } else { mark[benchesPos[2*i]]=true; benches.push_back(benchesPos[2*i]); } } } } return benches; } int find(int u) { if(u==P[u]) return u; return P[u]=find(P[u]); } void merge(int u,int v) { if(u>v) swap(u,v); P[u]=v; } vector<ii> removePaths(vector<ii> paths) { for(int i=0;i<n;i++) P[i]=i; vector<ii> newPaths; for(ii path:paths) { int u=find(path.first),v=find(path.second); if(u!=v) { merge(u,v); newPaths.push_back(path); } } return newPaths; } int construct_roads(std::vector<int> _x, std::vector<int> _y) { n=_x.size(); x=_x,y=_y; for(int i=0;i<n;i++) M[ii(x[i],y[i])]=i; vector<ii> paths; for(int i=0;i<n;i++) { auto it=M.find({x[i]+2,y[i]}); if(it!=M.end()) paths.push_back({i,it->second}); it=M.find({x[i],y[i]+2}); if(it!=M.end()) paths.push_back({i,it->second}); } sort(paths.begin(),paths.end(),cmp); paths = removePaths(paths); if(paths.size()!=n-1) return 0; //for(ii path:paths) // cerr<<x[path.first]<<' '<<y[path.first]<<' '<<x[path.second]<<' '<<y[path.second]<<'\n'; vector<ii> benches=constructBenches(paths); vector<int> U(n-1),V(n-1),A(n-1),B(n-1); for(int i=0;i<n-1;i++) { U[i]=paths[i].first,V[i]=paths[i].second; A[i]=benches[i].first,B[i]=benches[i].second; } build(U,V,A,B); return 1; }

Compilation message (stderr)

parks.cpp: In function 'std::vector<std::pair<int, int> > constructBenches(std::vector<std::pair<int, int> >&)':
parks.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<paths.size();i++) {
      |              ~^~~~~~~~~~~~~
parks.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0;i<paths.size();i++) {
      |               ~^~~~~~~~~~~~~
parks.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0;i<paths.size();i++) {
      |               ~^~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:120:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |  if(paths.size()!=n-1)
      |     ~~~~~~~~~~~~^~~~~
#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...