제출 #602388

#제출 시각아이디문제언어결과실행 시간메모리
602388rrrr10000분수 공원 (IOI21_parks)C++17
30 / 100
641 ms49908 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> PP; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<bool> vb; typedef vector<P> vp; typedef vector<vp> vvp; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++) #define fi first #define se second #define pb emplace_back #define all(a) a.begin(),a.end() template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;} template<class T> void out(T a){cout<<a<<endl;} template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;} vi dx={2,0,-2,0},dy={0,2,0,-2}; ll mx=200005; int construct_roads(std::vector<int> X, std::vector<int> Y) { if (X.size() == 1) { build({}, {}, {}, {}); return 1; } ll n=X.size(); map<P,ll> mp; rep(i,n)mp[P(X[i],Y[i])]=i; vp edge; rep(i,n)rep(j,2){ ll nx=X[i]+dx[j],ny=Y[i]+dy[j]; if(mp.count(P(nx,ny)))edge.pb(i,mp[P(nx,ny)]); } { vvi g(n); for(auto x:edge){ g[x.fi].pb(x.se); g[x.se].pb(x.fi); } queue<ll> que; vb done(n,false); done[0]=true; que.push(0); while(!que.empty()){ ll t=que.front();que.pop(); for(ll x:g[t])if(!done[x]){ done[x]=true;que.push(x); } } rep(i,n)if(!done[i])return 0; } vvp al(mx); rep(i,n)al[Y[i]].pb(X[i],i); rep(i,mx)sort(all(al[i])); vector<int> u, v, a, b; auto add=[&](ll i,ll j,ll t){ u.pb(i);v.pb(j); if(t==0||t==1){ assert(Y[i]==Y[j]); a.pb((X[i]+X[j])/2); if(t==0)b.pb(Y[i]-1); else b.pb(Y[i]+1); } else{ assert(X[i]==X[j]); b.pb((Y[i]+Y[j])/2); if(t==2)a.pb(X[i]-1); else a.pb(X[i]+1); } }; bool small=true; rep(i,n)if(X[i]>6)small=false; if(small){ vb tmp(2,false); rep(i,mx)if(al[i].size()){ vb ntmp(2,false); if(!al[i-2].size()){ rep(j,al[i].size()-1)if(al[i][j+1].fi-al[i][j].fi==2)add(al[i][j].se,al[i][j+1].se,0); } else{ if(al[i].back().fi==6&&al[i-2].back().fi==6)add(al[i].back().se,al[i-2].back().se,3); if(al[i][0].fi==2&&al[i-2][0].fi==2)add(al[i][0].se,al[i-2][0].se,2); if(al[i][0].fi==4&&al[i-2].back().fi==4){ add(al[i][0].se,al[i-2].back().se,3); if(al[i].size()>1){ add(al[i][0].se,al[i][1].se,1); ntmp[1]=true; } } else if(al[i].back().fi==4&&al[i-2][0].fi==4){ add(al[i].back().se,al[i-2][0].se,2); if(al[i].size()>1){ add(al[i][0].se,al[i][1].se,1); ntmp[0]=true; } } else if(al[i-2].size()==3&&al[i].size()==1&&al[i][0].fi==4){ if(tmp[1])add(al[i-2][1].se,al[i][0].se,2); else add(al[i-2][1].se,al[i][0].se,3); } else if(al[i-2].size()==1&&al[i-2][0].fi==4&&al[i].size()==3){ add(al[i-2][0].se,al[i][1].se,3); add(al[i][0].se,al[i][1].se,0); add(al[i][1].se,al[i][2].se,1); ntmp[1]=true; } else{ rep(j,al[i].size()-1)if(al[i][j+1].fi-al[i][j].fi==2){ ll t=al[i][j].fi/2-1; if(tmp[t]){ ntmp[t]=true;add(al[i][j].se,al[i][j+1].se,1); } else add(al[i][j].se,al[i][j+1].se,0); } } } tmp=ntmp; } build(u, v, a, b); return 1; } for(auto x:edge){ u.pb(x.fi);v.pb(x.se); P p((X[x.fi]+X[x.se])/2,(Y[x.fi]+Y[x.se])/2); if(X[x.fi]==X[x.se]){ p.fi++; if((p.fi+p.se)%4==2)p.fi-=2; } else{ p.se++; if((p.fi+p.se)%4==0)p.se-=2; } a.pb(p.fi);b.pb(p.se); } }

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

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:30:15: warning: control reaches end of non-void function [-Wreturn-type]
   30 |     map<P,ll> mp;
      |               ^~
#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...