Submission #8039

#	Time	Username	Problem	Language	Result	Execution time	Memory
8039		dohyun0324	Ideal city (IOI12_city)	C++98	100 / 100	124 ms	8448 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45