Submission #89968

#	Time	Username	Problem	Language	Result	Execution time	Memory
89968		nikolapesic2802	ČVENK (COI15_cvenk)	C++14	100 / 100	1730 ms	181736 KiB

cvenk

#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,ll velicina,ll x,ll y)
{
    //printf("%lld %lld, %lld\n",x,y,velicina);
    //cout << points << endl;
    vector<pair<int,int> > posle,levo,desno,gore;
    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&&p.second<y+velicina/2)
        {
            gore.pb(p);
            continue;
        }
        if(p.first>=x+velicina/2)
        {
            levo.pb(p);
        }
        else
        {
            desno.pb(p);
        }
    }
    if(gore.size())
    {
        construct(gore,velicina/2,x,y);
    }
    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,(ll)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()
{
    //show();
    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> >, long long int, long long int, long long int)':
cvenk.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(nxt>=graf.size())
            ~~~^~~~~~~~~~~~~
cvenk.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(nxt>=graf.size())
            ~~~^~~~~~~~~~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:163:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
cvenk.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40