제출 #435730

#제출 시각아이디문제언어결과실행 시간메모리
435730DanerZein분수 공원 (IOI21_parks)C++17
15 / 100
359 ms48644 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; typedef vector<ii> vi; const int MAX_N=2e5+10; vector<vi> ox(MAX_N),oy(MAX_N); int pa[MAX_N],tam[MAX_N]; void init(int n){ for(int i=0;i<n;i++){ pa[i]=i; tam[i]=1; } } int findset(int i){ if(pa[i]==i) return i; return pa[i]=findset(pa[i]); } bool issameset(int i,int j){ return findset(i)==findset(j); } void unionset(int i,int j){ if(!issameset(i,j)){ int u=findset(i),v=findset(j); pa[u]=v; tam[v]+=tam[u]; } } int construct_roads(std::vector<int> x, std::vector<int> y) { int n=x.size(); for(int i=0;i<n;i++){ ox[x[i]].push_back(ii(y[i],i)); oy[y[i]].push_back(ii(x[i],i)); } for(int i=0;i<MAX_N;i++){ sort(ox[i].begin(),ox[i].end()); sort(oy[i].begin(),oy[i].end()); } vector<int> ru,rv,ra,rb; set<ii> ba; init(n); for(int i=2;i<MAX_N;i+=2){ int t=oy[i].size(); for(int j=0;j<t-1;j++){ int xi=oy[i][j].first,xj=oy[i][j+1].first; int u=oy[i][j].second,v=oy[i][j+1].second; if(xj-xi==2 && !issameset(u,v)){ ru.push_back(oy[i][j].second); rv.push_back(oy[i][j+1].second); unionset(u,v); int xk=oy[i][j+2].first; auto it=lower_bound(oy[i-2].begin(),oy[i-2].end(),ii(xj,-1)); if(j+2<t && oy[i][j+2].first-xj==2 && it!=oy[i-2].end() && (*it).first==xj){ ra.push_back(xi+1); rb.push_back(i+1); ba.insert(ii(xi+1,i+1)); it=lower_bound(oy[i+2].begin(),oy[i+2].end(),ii(xi,-1)); int id=it-oy[i+2].begin(); if(it!=oy[i+2].end() && (*it).first==xi && id-1>=0 && oy[i+2][id].first-oy[i+2][id-1].first==2){ int uu=oy[i+2][id].second,vv=oy[i+2][id-1].second; unionset(uu,vv); ru.push_back(uu); rv.push_back(vv); ra.push_back(xi-1); rb.push_back(i+3); } } else{ ra.push_back(xi+1); rb.push_back(i-1); ba.insert(ii(xi+1,i-1)); } } } } for(int i=2;i<MAX_N;i+=2){ int t=ox[i].size(); for(int j=0;j<t-1;j++){ int yi=ox[i][j].first,yj=ox[i][j+1].first; int u=ox[i][j].second,v=ox[i][j+1].second; if(yj-yi==2){ ru.push_back(u); rv.push_back(v); unionset(u,v); if(ba.find(ii(i-1,yi+1))!=ba.end()){ ra.push_back(i+1); rb.push_back(yi+1); ba.insert(ii(i+1,yi+1)); } else{ ra.push_back(i-1); rb.push_back(yi+1); ba.insert(ii(i-1,yi+1)); } } } } if(tam[findset(0)]!=n) return 0; build(ru,rv,ra,rb); return 1; }

컴파일 시 표준 에러 (stderr) 메시지

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:50:6: warning: unused variable 'xk' [-Wunused-variable]
   50 |  int xk=oy[i][j+2].first;
      |      ^~
#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...