Submission #16271

#	Time	Username	Problem	Language	Result	Execution time	Memory
16271		atomzeno	Ideal city (IOI12_city)	C++98	100 / 100	101 ms	11056 KiB

city

#include<algorithm>
#define MX 100001
#define MOD 1000000000
#include<vector>
using namespace std;
int n,check[MX],cnt,num[MX],checking[MX],numing[MX];
long long int ans;
vector<int> A[MX];
struct DT{
    long long int x,y;
};
bool cmpx(const DT&r1,const DT&r2){
    if(r1.x==r2.x)return r1.y<r2.y;
    return r1.x<r2.x;
}
bool cmpy(const DT&r1,const DT&r2){
    if(r1.y==r2.y)return r1.x<r2.x;
    return r1.y<r2.y;
}
DT a[MX];
int what(int x1,int y1,int x2,int y2,int cmp){
    if(cmp==0){
        if(x1>x2){return 1;}
        else if(x1==x2&&y1>=y2){return 1;}
        return 0;
    }
    else{
        if(y1>y2){return 1;}
        else if(x1>=x2&&y1==y2){return 1;}
        return 0;
    }
}
void bck(int x){
    int i=0;
    checking[x]=1;
    for(i=0;i<(int)A[x].size();i++){
        if(checking[A[x][i]]==0){
            bck(A[x][i]);
            num[x]+=num[A[x][i]];
        }
    }
    num[x]+=numing[x];
    ans+=((long long int)num[x]*(n-num[x]));
    ans%=MOD;
}
int finding(int x,int y,int z){
    int s=0,e=n,m;
    for(;;){
        if((s+1)==e){break;}
        m=(s+e)/2;
        if(what(x,y,a[m].x,a[m].y,z)==1){
            s=m;
        }
        else{
            e=m;
        }
    }
    if(a[s].x==x&&a[s].y==y){return s;}
    return -1;
}
int DistanceSum(int N, int *X, int *Y){
    int i,cnt,o;
    n=N;
    for(i=0;i<n;i++){a[i].x=X[i],a[i].y=Y[i];}
    sort(a,a+n,cmpx);
    cnt=0;
    a[n].x=(long long int)1<<33,a[n].y=(long long int)1<<33;
    for(i=0;i<n;i++){
        if(a[i].x==a[i+1].x&&(a[i].y+1)==a[i+1].y){
            check[i]=check[i+1]=cnt;
        }
        else{
            check[i+1]=++cnt;
        }
    }
    cnt--;
    for(i=0;i<n;i++){
        numing[check[i]]++;
    }
    for(i=0;i<n;i++){
        o=finding(a[i].x+1,a[i].y,0);
        if(o!=-1){
            A[check[i]].push_back(check[o]);
            A[check[o]].push_back(check[i]);
        }
    }
    bck(0);
    sort(a,a+n,cmpy);
    cnt=0;
    a[n].x=(long long int)1<<33,a[n].y=(long long int)1<<33;
    for(i=0;i<n;i++){
        if((a[i].x+1)==a[i+1].x&&a[i].y==a[i+1].y){
            check[i]=check[i+1]=cnt;
        }
        else{
            check[i+1]=++cnt;
        }
    }
    cnt--;
    for(i=0;i<=n;i++){
        numing[i]=num[i]=0;
        while(((int)A[i].size())){
            A[i].pop_back();
        }
        checking[i]=0;
    }
    for(i=0;i<n;i++){
        numing[check[i]]++;
    }
    for(i=0;i<n;i++){
        o=finding(a[i].x,a[i].y+1,1);
        if(o!=-1){
            A[check[i]].push_back(check[o]);
            A[check[o]].push_back(check[i]);
        }
    }
    bck(0);
    return ans;
}

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