Submission #901573

#TimeUsernameProblemLanguageResultExecution timeMemory
901573JakobZorzIdeal city (IOI12_city)C++17
23 / 100
128 ms27580 KiB
#include<iostream> #include<vector> #include<limits.h> #include<unordered_set> #include<map> using namespace std; typedef long long ll; const int MOD=1e9; const int BIG=INT_MAX; int w,h; vector<unordered_set<int>>cols; map<pair<int,int>,bool>vis; struct Tree{ int val=0; vector<Tree*>ch; pair<int,int>sum; bool sumt=false; int get(){ vector<int>vals; for(auto c:ch){ auto r=c->get_sum(); vals.push_back(r.first+r.second); } int res=0; for(int i=0;i<(int)vals.size();i++){ for(int j=i-1;j>=0;j--){ res=(res+(ll)vals[i]*vals[j]*2)%MOD; } } for(int i:vals) res=(res+(ll)i*val)%MOD; for(auto c:ch){ res+=c->get(); res%=MOD; } return res; } pair<int,int>get_sum(){ // (num_nodes,sum_of_paths) if(sumt) return sum; sum={val,0}; for(auto c:ch){ auto r=c->get_sum(); sum.first+=r.first; sum.second+=(r.second+r.first)%MOD; sum.second%=MOD; } sumt=true; return sum; } }; Tree*get_tree(int x,int y){ if(vis[{x,y}]) return nullptr; if(x<0||x>=w) return nullptr; if(cols[x].find(y)==cols[x].end()) return nullptr; vis[{x,y}]=true; Tree*res=new Tree; res->val=1; int cy=y-1; while(cols[x].find(cy)!=cols[x].end()){ vis[{x,cy}]=true; cy--; res->val++; } cy=y+1; while(cols[x].find(cy)!=cols[x].end()){ vis[{x,cy}]=true; cy++; res->val++; } { auto r=get_tree(x+1,y); if(r) res->ch.push_back(r); } { auto r=get_tree(x-1,y); if(r) res->ch.push_back(r); } cy=y-1; while(cols[x].find(cy)!=cols[x].end()){ { auto r=get_tree(x+1,cy); if(r) res->ch.push_back(r); } { auto r=get_tree(x-1,cy); if(r) res->ch.push_back(r); } cy--; } cy=y+1; while(cols[x].find(cy)!=cols[x].end()){ { auto r=get_tree(x+1,cy); if(r) res->ch.push_back(r); } { auto r=get_tree(x-1,cy); if(r) res->ch.push_back(r); } cy++; } return res; } int get_dist(vector<pair<int,int>>vec){ w=0; h=0; for(auto i:vec){ w=max(w,i.first+1); h=max(h,i.second+1); } cols.clear(); cols.resize(w); vis.clear(); for(auto i:vec) cols[i.first].insert(i.second); Tree*tree=get_tree(0,*cols[0].begin()); int r=tree->get(); return r; } int DistanceSum(int N,int *X,int *Y){ int mx=BIG,my=BIG; for(int i=0;i<N;i++){ mx=min(mx,X[i]); my=min(my,Y[i]); } vector<pair<int,int>>vec1,vec2; for(int i=0;i<N;i++){ vec1.emplace_back(X[i]-mx,Y[i]-my); vec2.emplace_back(Y[i]-my,X[i]-mx); } return(get_dist(vec1)+get_dist(vec2))%MOD; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...