Submission #817215

#TimeUsernameProblemLanguageResultExecution timeMemory
817215penguinmanFountain Parks (IOI21_parks)C++17
45 / 100
540 ms53824 KiB
#include "parks.h" #include <bits/stdc++.h> using std::cin; using std::cout; using std::vector; using std::string; using ll = int; using vi = vector<ll>; using vii = vector<vi>; using pii = std::pair<ll,ll>; using std::endl; #define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++) #define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++) #define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--) #define ln "\n" #define pb emplace_back #define mp std::make_pair #define all(a) a.begin(),a.end() int construct_roads(std::vector<int> x, std::vector<int> y) { { vi u,v,a,b; vi par(x.size()); rep(i,0,x.size()) par[i] = i; std::function<ll(ll)> root = [&](ll now){ if(par[now] == now) return now; return par[now] = root(par[now]); }; std::map<ll,std::map<ll,ll>> X, Y; rep(i,0,x.size()) X[x[i]][y[i]] = Y[y[i]][x[i]] = i; for(auto V: X){ for(auto el: V.second){ if(V.second.count(el.first+2)){ ll now = el.second; ll next = V.second[el.first+2]; if(root(now) == root(next)) continue; par[root(now)] = root(next); vi P = {1,-1}; rep(i,0,2){ ll ry = el.first+1; ll rx = V.first+P[i]; if((rx+ry)%4 == 0){ u.pb(now); v.pb(next); a.pb(rx); b.pb(ry); } } } } } for(auto V: Y){ for(auto el: V.second){ if(V.second.count(el.first+2)){ ll now = el.second; ll next = V.second[el.first+2]; if(root(now) == root(next)) continue; par[root(now)] = root(next); vi P = {1,-1}; rep(i,0,2){ ll rx = el.first+1; ll ry = V.first+P[i]; if((rx+ry)%4 == 2){ u.pb(now); v.pb(next); a.pb(rx); b.pb(ry); } } } } } if(u.size()+1 == x.size()){ build(u,v,a,b); return 1; } } return 0; if(*max_element(all(x)) <= 6){ vector<std::map<ll,ll>> X(7); rep(i,0,x.size()){ X[x[i]][y[i]] = i; } vi u,v,a,b; vi par(x.size()); rep(i,0,x.size()) par[i] = i; std::function<ll(ll)> root = [&](ll now){ if(par[now] == now) return now; return par[now] = root(par[now]); }; for(auto el: X[2]){ if(X[2].count(el.first+2)){ u.pb(el.second); ll next = X[2][el.first+2]; v.pb(next); a.pb(1); b.pb(el.first+1); par[root(el.second)] = root(next); } } for(auto el: X[6]){ if(X[6].count(el.first+2)){ u.pb(el.second); ll next = X[6][el.first+2]; v.pb(next); a.pb(7); b.pb(el.first+1); par[root(el.second)] = root(next); } } std::set<pii> used; for(auto el: X[4]){ if(X[4].count(el.first+2)){ ll next = X[4][el.first+2]; par[root(next)] = root(el.second); ll rx = -1, ry = -1; if(el.first%4 == 0) rx = 3, ry = el.first+1; if(el.first%4 == 2) rx = 5, ry = el.first+1; used.insert(mp(rx, ry)); u.pb(el.second); v.pb(next); a.pb(rx); b.pb(ry); } } for(auto el: X[4]){ if(X[2].count(el.first)){ ll next = X[2][el.first]; if(root(next) != root(el.second)){ par[root(next)] = root(el.second); u.pb(el.second); v.pb(next); ll rx = -1, ry = -1; if(!used.count(mp(3,el.first-1))) rx = 3, ry = el.first-1; if(!used.count(mp(3,el.first+1))) rx = 3, ry = el.first+1; assert(rx != -1); a.pb(rx); b.pb(ry); used.insert(mp(rx, ry)); } } if(X[6].count(el.first)){ ll next = X[6][el.first]; if(root(next) != root(el.second)){ par[root(next)] = root(el.second); u.pb(el.second); v.pb(next); ll rx = -1, ry = -1; if(!used.count(mp(5,el.first-1))) rx = 5, ry = el.first-1; if(!used.count(mp(5,el.first+1))) rx = 5, ry = el.first+1; assert(rx != -1); a.pb(rx); b.pb(ry); used.insert(mp(rx, ry)); } } } if(u.size()+1 == x.size()){ build(u,v,a,b); return 1; } else return 0; } std::map<pii,ll> xy; std::map<pii,ll> rev; rep(i,0,x.size()) xy[mp(x[i],y[i])] = i; ll cnt__ = 0; rep(i,0,x.size()){ vi P = {2,0}, Q = {0,2}; vi R = {0,1}, S = {1,0}; rep(j,0,2){ if(xy.count(mp(x[i]+P[j], y[i]+Q[j]))){ ll mx = x[i]+P[j]/2; ll my = y[i]+Q[j]/2; rev[mp(mx+R[j], my+S[j])] = rev[mp(mx-R[j],my-S[j])] = 0; cnt__++; } } } ll N = 0; vi rx, ry; for(auto &el: rev){ el.second = N++; rx.pb(el.first.first); ry.pb(el.first.second); } vii edge(N); vii eu(N), ev(N); rep(i,0,x.size()){ vi P = {2,0}, Q = {0,2}; vi R = {0,1}, S = {1,0}; rep(j,0,2){ if(xy.count(mp(x[i]+P[j], y[i]+Q[j]))){ ll mx = x[i]+P[j]/2; ll my = y[i]+Q[j]/2; ll nu = rev[mp(mx+R[j], my+S[j])]; ll nv = rev[mp(mx-R[j],my-S[j])]; ll nxy = xy[mp(x[i]+P[j], y[i]+Q[j])]; edge[nu].pb(nv); eu[nu].pb(i); ev[nu].pb(nxy); edge[nv].pb(nu); eu[nv].pb(i); ev[nv].pb(nxy); } } } vi cnt(N); rep(i,0,N) cnt[i] = edge[i].size(); vi u,v,a,b; rep(k,0,N){ if(cnt[k] != 1) continue; cnt[k]--; ll now = k; while(true){ ll nex = -1; rep(i,0,edge[now].size()){ ll next = edge[now][i]; if(cnt[next] == 0) continue; u.pb(eu[now][i]); v.pb(ev[now][i]); a.pb(rx[now]); b.pb(ry[now]); cnt[next]--; if(cnt[next] == 1){ cnt[next]--; nex = next; } } if(nex == -1) break; now = nex; } } rep(i,0,N){ if(cnt[i] > 2) return 0; } rep(i,0,N){ assert(cnt[i] == 0 || cnt[i] == 2); if(cnt[i] == 0) continue; cnt[i] = 0; ll now = i; while(true){ ll val = -1; rep(j,0,edge[now].size()){ ll next = edge[now][j]; if(cnt[next] == 0) continue; u.pb(eu[now][j]); v.pb(ev[now][j]); a.pb(rx[now]); b.pb(ry[now]); val = cnt[next]; cnt[next] = 0; now = next; break; } if(val == -1) break; } rep(j,0,edge[now].size()){ ll next = edge[now][j]; if(next != i) continue; u.pb(eu[now][j]); v.pb(ev[now][j]); a.pb(rx[now]); b.pb(ry[now]); } } build(u,v,a,b); return 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...