oj.uz

Submission #8039

# Submission time Handle Problem Language Result Execution time Memory
8039 2014-08-27T14:37:39 Z dohyun0324 Ideal city (IOI12_city) C++
100 / 100
 124 ms 8448 KB 
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
map<int,int>ch;
int w,N,pos[100010],p,k,cnt,s,e,sw,val,st[100010],top,dp[100010],len[100010],n,check[100010];
long long dap;
struct data{
    int x,y;
    bool operator<(const data&r)const{
        if(x==r.x) return y<r.y;
        return x<r.x;
    }
}a[100010];
struct data2{
    int x,y;
    bool operator<(const data2&r)const{
        if(x==r.x) return y<r.y;
        return x<r.x;
    }
}con[100010];
void uw(int i)
{
    int j;
    cnt++; sw=0;
    for(j=k;j<=i;j++){
        if(s==0 && e==0) break;
        if(ch[a[j].y]>=s && sw==0){w++; con[w].x=cnt; con[w].y=ch[a[j].y]; sw=1;}
        if(ch[a[j].y]<s) sw=0;
    }
    len[cnt]=i-k+1;
    k=i+1;
}
void dfs(int x)
{
    int i;
    check[x]=1;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(check[con[i].y]==1) continue;
        dfs(con[i].y);
        dp[x]+=dp[con[i].y];
    }
    dp[x]+=len[x];
    dap+=(long long)dp[x]*(long long)(n-dp[x]);
    dap%=1000000000;
}
int DistanceSum(int N, int *X, int *Y)
{
    n=N;
    int i,j;
    for(i=0;i<N;i++) a[i].x=X[i], a[i].y=Y[i];
    sort(a,a+N);
    for(i=0;i<N;i++)
    {
        if(a[i].x==a[i+1].x && a[i+1].y!=a[i].y+1) st[++top]=i;
        if(a[i].x!=a[i+1].x)
        {
            st[++top]=i;
            for(j=1;j<=top;j++) uw(st[j]);
            s=e+1; e=cnt; val=s; top=0;
            for(j=p;j<=i;j++){
                ch[a[j].y]=val;
                if(a[j+1].y!=a[j].y+1) val++;
            }
            p=i+1;
        }
    }
    for(i=w+1;i<=w*2;i++)
    {
        con[i].x=con[i-w].y; con[i].y=con[i-w].x;
    }
    w*=2;
    sort(con+1,con+w+1);
    for(i=1;i<=w;i++){
        if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
    }
    dfs(1);

    for(i=0;i<N;i++) a[i].y=X[i], a[i].x=Y[i];
    sort(a,a+N);
    top=0; memset(len,0,sizeof len); memset(dp,0,sizeof dp); memset(con,0,sizeof con); w=0; p=0; cnt=0; s=0; e=0;
    memset(check,0,sizeof check); ch.clear();
    for(i=0;i<N;i++)
    {
        if(a[i].x==a[i+1].x && a[i+1].y!=a[i].y+1) st[++top]=i;
        if(a[i].x!=a[i+1].x)
        {
            st[++top]=i;
            for(j=1;j<=top;j++) uw(st[j]);
            s=e+1; e=cnt; val=s; top=0;
            for(j=p;j<=i;j++){
                ch[a[j].y]=val;
                if(a[j+1].y!=a[j].y+1) val++;
            }
            p=i+1;
        }
    }
    for(i=w+1;i<=w*2;i++)
    {
        con[i].x=con[i-w].y; con[i].y=con[i-w].x;
    }
    w*=2;
    sort(con+1,con+w+1);
    for(i=1;i<=w;i++){
        if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
    }
    dfs(1);
    return dap;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4932 KB Output is correct
2 Correct 12 ms 4932 KB Output is correct
3 Correct 36 ms 5252 KB Output is correct
4 Correct 32 ms 5252 KB Output is correct
5 Correct 76 ms 5644 KB Output is correct
6 Correct 68 ms 5644 KB Output is correct
7 Correct 60 ms 5644 KB Output is correct
8 Correct 76 ms 5644 KB Output is correct
9 Correct 72 ms 5800 KB Output is correct
10 Correct 76 ms 8448 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4932 KB Output is correct
2 Correct 16 ms 4932 KB Output is correct
3 Correct 60 ms 5252 KB Output is correct
4 Correct 52 ms 5252 KB Output is correct
5 Correct 124 ms 5644 KB Output is correct
6 Correct 92 ms 5700 KB Output is correct
7 Correct 116 ms 5684 KB Output is correct
8 Correct 96 ms 5644 KB Output is correct
9 Correct 88 ms 5644 KB Output is correct
10 Correct 88 ms 5644 KB Output is correct