Submission #1046607

#TimeUsernameProblemLanguageResultExecution timeMemory
1046607UnforgettableplFountain Parks (IOI21_parks)C++17
0 / 100
0 ms348 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; int construct_roads(vector<int> x,vector<int> y){ int n = x.size(); map<pair<int,int>,int> lookup; for(int i=0;i<n;i++)lookup[{x[i],y[i]}]=i; vector<int> u,v,a,b; vector<vector<int>> adj(1); vector<tuple<int,int,int,int>> edges; edges.emplace_back(0,0,0,0); int S = 0; for(int i=0;i<n;i++){ if(lookup.count({x[i]+2,y[i]})){ S++; adj.emplace_back(); edges.emplace_back(i,lookup[{x[i]+2,y[i]}],x[i]+1,y[i]-1); if(lookup.count({x[i]+1,y[i]-1})){ adj[S].emplace_back(lookup[{x[i]+1,y[i]-1}]); adj[lookup[{x[i]+1,y[i]-1}]].emplace_back(S); } else lookup[{x[i]+1,y[i]-1}]=S; S++; adj.emplace_back(); edges.emplace_back(i,lookup[{x[i]+2,y[i]}],x[i]+1,y[i]+1); if(lookup.count({x[i]+1,y[i]+1})){ adj[S].emplace_back(lookup[{x[i]+1,y[i]+1}]); adj[lookup[{x[i]+1,y[i]+1}]].emplace_back(S); } else lookup[{x[i]+1,y[i]+1}]=S; adj[S].emplace_back(S-1); adj[S-1].emplace_back(S); } if(lookup.count({x[i],y[i]-2})){ S++; adj.emplace_back(); edges.emplace_back(i,lookup[{x[i],y[i]-2}],x[i]-1,y[i]-1); if(lookup.count({x[i]-1,y[i]-1})){ adj[S].emplace_back(lookup[{x[i]-1,y[i]-1}]); adj[lookup[{x[i]-1,y[i]-1}]].emplace_back(S); } else lookup[{x[i]-1,y[i]-1}]=S; S++; adj.emplace_back(); edges.emplace_back(i,lookup[{x[i],y[i]-2}],x[i]+1,y[i]-1); if(lookup.count({x[i]+1,y[i]-1})){ adj[S].emplace_back(lookup[{x[i]+1,y[i]-1}]); adj[lookup[{x[i]+1,y[i]-1}]].emplace_back(S); } else lookup[{x[i]+1,y[i]-1}]=S; adj[S].emplace_back(S-1); adj[S-1].emplace_back(S); } } vector<int> colour(S+1,-1); bool works = true; function<void(int,int)> dfs = [&](int x,int col){ if(colour[x]!=-1){ if(colour[x]!=col)works=false; return; } colour[x]=col; for(int&i:adj[x])dfs(i,col^1); }; for(int i=1;i<=S;i++)if(colour[i]==-1)dfs(i,0); if(!works)return 0; for(int i=1;i<=S;i++){ if(colour[i]==0)continue; auto [c,d,e,f] = edges[i]; u.emplace_back(c); v.emplace_back(d); a.emplace_back(e); b.emplace_back(f); } 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...