oj.uz

Submission #16271

# Submission time Handle Problem Language Result Execution time Memory
16271 2015-08-19T09:04:11 Z atomzeno Ideal city (IOI12_city) C++
100 / 100
 101 ms 11056 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6676 KB Output is correct
2 Correct 0 ms 6676 KB Output is correct
3 Correct 0 ms 6676 KB Output is correct
4 Correct 0 ms 6808 KB Output is correct
5 Correct 0 ms 6808 KB Output is correct
6 Correct 0 ms 6808 KB Output is correct
7 Correct 0 ms 6808 KB Output is correct
8 Correct 0 ms 6808 KB Output is correct
9 Correct 0 ms 6808 KB Output is correct
10 Correct 0 ms 6808 KB Output is correct
11 Correct 0 ms 6808 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6808 KB Output is correct
2 Correct 0 ms 6808 KB Output is correct
3 Correct 0 ms 6812 KB Output is correct
4 Correct 0 ms 6812 KB Output is correct
5 Correct 3 ms 6812 KB Output is correct
6 Correct 0 ms 6812 KB Output is correct
7 Correct 4 ms 6812 KB Output is correct
8 Correct 0 ms 6812 KB Output is correct
9 Correct 0 ms 6812 KB Output is correct
10 Correct 3 ms 6812 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7148 KB Output is correct
2 Correct 15 ms 7412 KB Output is correct
3 Correct 46 ms 7728 KB Output is correct
4 Correct 44 ms 8136 KB Output is correct
5 Correct 86 ms 8780 KB Output is correct
6 Correct 89 ms 9924 KB Output is correct
7 Correct 88 ms 9440 KB Output is correct
8 Correct 74 ms 8784 KB Output is correct
9 Correct 90 ms 9356 KB Output is correct
10 Correct 87 ms 11056 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7280 KB Output is correct
2 Correct 22 ms 7280 KB Output is correct
3 Correct 46 ms 7992 KB Output is correct
4 Correct 45 ms 7992 KB Output is correct
5 Correct 99 ms 9176 KB Output is correct
6 Correct 93 ms 9364 KB Output is correct
7 Correct 101 ms 9216 KB Output is correct
8 Correct 94 ms 9176 KB Output is correct
9 Correct 88 ms 9176 KB Output is correct
10 Correct 90 ms 9308 KB Output is correct