Submission #89966

#TimeUsernameProblemLanguageResultExecution timeMemory
89966nikolapesic2802ČVENK (COI15_cvenk)C++14
0 / 100
110 ms59164 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll long long #define pb push_back #define sz(x) (int)(x).size() #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key() template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& a) { os << '{'; for(int i=0;i<sz(a);i++) { if(i>0&&i<sz(a)-1) os << ", "; os << a[i]; } os << '}'; return os; } void show() { int n=128; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i&j) printf("%c",178); else printf("%c",176); } printf("\n"); } } map<int,pair<int,int> > mapax,mapay; ///{kordinata,poz_u_grafu} int nxt=1; vector<pair<int,int> > dummy; int dummy1; vector<vector<pair<int,int> > > graf(2); vector<int> cnt(2); void construct(vector<pair<int,int> > points,int velicina,int x,int y) { //printf("%i %i, %i\n",x,y,velicina); //cout << points << endl; vector<pair<int,int> > posle,levo,desno; for(auto p:points) { assert(p.first>=x&&p.second>=y); if(p.first>=x+velicina||p.second>=y+velicina){ posle.pb(p); continue; } if(p.first>=x+velicina/2) { levo.pb(p); } else { desno.pb(p); } } if(levo.size()) { //assert(mapay[y].first<x+velicina/2); graf[mapay[y].second].pb({nxt,x+velicina/2-mapay[y].first}); mapay[y]=make_pair(x+velicina/2,nxt); mapax[x+velicina/2]=make_pair(y,nxt); vector<pair<int,int> > ne; for(auto p:levo) { if(p.first==x+velicina/2&&p.second==y) cnt[nxt]++; else ne.pb(p); } nxt++; if(nxt>=graf.size()) graf.pb(dummy),cnt.pb(dummy1); if(ne.size()) construct(ne,velicina/2,x+velicina/2,y); } if(desno.size()) { //assert(mapax[x].first<y+velicina/2); graf[mapax[x].second].pb({nxt,y+velicina/2-mapax[x].first}); mapax[x]=make_pair(y+velicina/2,nxt); mapay[y+velicina/2]=make_pair(x,nxt); vector<pair<int,int> > ne; for(auto p:desno) { if(p.first==x&&p.second==y+velicina/2) cnt[nxt]++; else ne.pb(p); } nxt++; if(nxt>=graf.size()) graf.pb(dummy),cnt.pb(dummy1); if(ne.size()) construct(ne,velicina/2,x,y+velicina/2); } if(posle.size()) { construct(posle,velicina*2,x,y); } } void printgraf(int tr) { printf("Cnt od %i: %i\n",tr,cnt[tr]); for(auto p:graf[tr]) { printf("Idem od %i do %i, tezina: %i\n",tr,p.first,p.second); printgraf(p.first); } } vector<int> siz; vector<ll> val; void postavi(int tr) { siz[tr]+=cnt[tr]; for(auto p:graf[tr]) { postavi(p.first); siz[tr]+=siz[p.first]; val[tr]+=val[p.first]+(ll)siz[p.first]*p.second; } } ll minn; void get_min(int tr,ll value) { minn=min(minn,value); for(auto p:graf[tr]) { ll ne=value-(ll)siz[p.first]*p.second; ne+=(ll)(siz[0]-siz[p.first])*p.second; get_min(p.first,ne); } } int main() { int n; scanf("%i",&n); vector<pair<int,int> > points; for(int i=0;i<n;i++){ int x,y; scanf("%i %i",&x,&y); if(x==0&&y==0) cnt[0]++; else points.pb({x,y}); } mapax[0]=make_pair(0,0); mapay[0]=make_pair(0,0); construct(points,2,0,0); //printgraf(0); int N=graf.size(); siz.resize(N); val.resize(N); postavi(0); minn=val[0]; /*for(int i=0;i<N;i++) { printf("%i: %i %lld\n",i,siz[i],val[i]); }*/ get_min(0,minn); printf("%lld\n",minn); return 0; }

Compilation message (stderr)

cvenk.cpp: In function 'void construct(std::vector<std::pair<int, int> >, int, int, int)':
cvenk.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(nxt>=graf.size())
            ~~~^~~~~~~~~~~~~
cvenk.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(nxt>=graf.size())
            ~~~^~~~~~~~~~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:153:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
cvenk.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...