Submission #251256

#	Time	Username	Problem	Language	Result	Execution time	Memory
251256		eohomegrownapps	Ideal city (IOI12_city)	C++14	32 / 100	781 ms	4096 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int m = 1000000000;
int INFi = 1e9;
unordered_set<ll> s_orig;

ll hashval(int x, int y){
    return x*(1LL<<31)+y;
}

ll bfs(int startx, int starty){
    unordered_set<ll> unvisited = s_orig;
    unvisited.erase(hashval(startx,starty));
    queue<pair<pair<int,int>,ll>> q;
    q.push({{startx,starty},0});
    ll total = 0;
    while (q.size()>0){
        auto f = q.front();
        q.pop();
        int x = f.first.first;
        int y = f.first.second;
        int dist = f.second;
        for (int i = 0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            auto f = unvisited.find(hashval(nx,ny));
            if (f!=unvisited.end()){
                unvisited.erase(f);
                total+=dist+1;
                q.push({{nx,ny},dist+1});
            }
        }
    }
    return total;
}

int subtask2(int n, int *x, int *y){
    for (int i = 0; i<n; i++){
        s_orig.insert(hashval(x[i],y[i]));
    }
    ll tot = 0;
    for (int i = 0; i<n; i++){
        tot += bfs(x[i],y[i]);
    }
    tot/=2;
    //cout<<"correct: "<<tot<<'\n';
    return tot%m;
}

int *xv, *yv;

bool cmpltr(int i, int j){
    if (yv[i]==yv[j]){
        return xv[i]<xv[j];
    } else {
        return yv[i]<yv[j];
    }
}

bool cmprtl(int i, int j){
    if (yv[i]==yv[j]){
        return xv[i]>xv[j];
    } else {
        return yv[i]<yv[j];
    }
}

int subtask3(int n, int *x, int *y){
    xv=x;yv=y;
    vector<int> order(n);
    for (int i = 0; i<n; i++){
        order[i]=i;
    }
    ll tot = 0;
    //ltr
    sort(order.begin(),order.end(),cmpltr);
    unordered_map<ll,ll> nltr;
    for (int i = 0; i<n; i++){
        int ind = order[i];
        ll cur = hashval(x[ind],y[ind]);
        ll curl = hashval(x[ind]-1,y[ind]);
        ll curu = hashval(x[ind],y[ind]-1);
        ll curlu = hashval(x[ind]-1,y[ind]-1);
        nltr[cur]=1;
        int chk = 0;
        if (nltr.find(curl)!=nltr.end()){
            nltr[cur]+=nltr[curl];
            chk++;
        }
        if (nltr.find(curu)!=nltr.end()){
            nltr[cur]+=nltr[curu];
            chk++;
        }
        if (chk==2&&nltr.find(curlu)!=nltr.end()){
            nltr[cur]-=nltr[curlu];
        }
    }
    unordered_map<ll,ll> cntltr;
    for (int i = 0; i<n; i++){
        int ind = order[i];
        ll cur = hashval(x[ind],y[ind]);
        ll curl = hashval(x[ind]-1,y[ind]);
        ll curu = hashval(x[ind],y[ind]-1);
        ll curlu = hashval(x[ind]-1,y[ind]-1);
        cntltr[cur]=0;
        int chk=0;
        if (nltr.find(curl)!=nltr.end()){
            cntltr[cur]+=nltr[curl]+cntltr[curl];
            chk++;
        }
        if (nltr.find(curu)!=nltr.end()){
            cntltr[cur]+=nltr[curu]+cntltr[curu];
            chk++;
        }
        if (chk==2&&nltr.find(curlu)!=nltr.end()){
            cntltr[cur]-=nltr[curlu]*2+cntltr[curlu];
        }
        tot+=cntltr[cur];
    }
    //cout<<tot<<'\n';
    sort(order.begin(),order.end(),cmprtl);
    unordered_map<ll,ll> nrtl;
    for (int i = 0; i<n; i++){
        int ind = order[i];
        ll cur = hashval(x[ind],y[ind]);
        ll curl = hashval(x[ind]+1,y[ind]);
        ll curu = hashval(x[ind],y[ind]-1);
        ll curlu = hashval(x[ind]+1,y[ind]-1);
        nrtl[cur]=1;
        int chk = 0;
        if (nrtl.find(curl)!=nrtl.end()){
            nrtl[cur]+=nrtl[curl];
            chk++;
        }
        if (nrtl.find(curu)!=nrtl.end()){
            nrtl[cur]+=nrtl[curu];
            chk++;
        }
        if (chk==2&&nrtl.find(curlu)!=nrtl.end()){
            nrtl[cur]-=nrtl[curlu];
        }
    }
    unordered_map<ll,ll> cntrtl;
    for (int i = 0; i<n; i++){
        int ind = order[i];
        ll cur = hashval(x[ind],y[ind]);
        ll curl = hashval(x[ind]+1,y[ind]);
        ll curu = hashval(x[ind],y[ind]-1);
        ll curlu = hashval(x[ind]+1,y[ind]-1);
        cntrtl[cur]=0;
        int chk = 0;
        if (nrtl.find(curl)!=nrtl.end()){
            cntrtl[cur]+=nrtl[curl]+cntrtl[curl];
            chk++;
        }
        if (nrtl.find(curu)!=nrtl.end()){
            cntrtl[cur]+=nrtl[curu]+cntrtl[curu];
            chk++;
        }
        if (chk==2&&nrtl.find(curlu)!=nrtl.end()){
            cntrtl[cur]-=nrtl[curlu]*2+cntrtl[curlu];
        }
        tot+=cntrtl[cur];
    }
    //cout<<tot<<'\n';
    //now take away double counting
    //horizontal
    unordered_map<int,pair<int,int>> yx;
    unordered_map<int,pair<int,int>> xy;
    for (int i = 0; i<n; i++){
        if (yx.find(y[i])==yx.end()){
            yx[y[i]]={INFi,-INFi};
        }
        if (xy.find(x[i])==xy.end()){
            xy[x[i]]={INFi,-INFi};
        }
        yx[y[i]].first=min(yx[y[i]].first,x[i]);
        yx[y[i]].second=max(yx[y[i]].first,x[i]);
        xy[x[i]].first=min(xy[x[i]].first,y[i]);
        xy[x[i]].second=max(xy[x[i]].first,y[i]);
    }
    for (auto p : yx){
        int minv = p.second.first;
        int maxv = p.second.second;
        //cout<<minv<<" "<<maxv<<'\n';
        int len = maxv-minv+1;
        ll tt = len*(len-1)*(len+1)/6;
        tot-=tt;
    }
    for (auto p : xy){
        int minv = p.second.first;
        int maxv = p.second.second;
        //cout<<minv<<" "<<maxv<<'\n';
        int len = maxv-minv+1;
        ll tt = len*(len-1)*(len+1)/6;
        tot-=tt;
    }
    //cout<<tot<<'\n';
    return tot;
}


int DistanceSum(int n, int *x, int *y) {
    if (n<=2000){
        //assert(subtask2(n,x,y)==subtask3(n,x,y));
        return subtask2(n,x,y);
    } else {
        return subtask3(n,x,y);
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45