Submission #18847

#	Time	Username	Problem	Language	Result	Execution time	Memory
18847		ggoh	Ideal city (IOI12_city)	C++98	100 / 100	51 ms	15584 KiB

city

#include<cstdio>
#include<algorithm>
#include<vector>
int a,xx,yy,i,j,p,q,back,t,x[100002],y[100002];
long long sum,mod=1e9,sz[100002];
std::vector<int>G[100002],E[100002];
struct A{
    int num,s,e;
};
std::vector<A>T[100002];

void dfs(int r,int par)
{
    for(int k=0;k<E[r].size();k++)
    {
        if(par==E[r][k])continue;
        dfs(E[r][k],r);
        sz[r]+=sz[E[r][k]];
    }
    sum+=sz[r]*(long long)(a-sz[r]);
}
void f()
{
    t=0;
    for(i=0;i<=a;i++)G[i].clear(),T[i].clear(),E[i].clear();
    for(i=1;i<=a;i++)
    {
        G[x[i]].push_back(y[i]);
    }
    for(i=0;G[i].size();i++)std::sort(G[i].begin(),G[i].end());
    for(i=0;G[i].size();i++)
    {
        back=G[i][0];
        for(j=0;j<G[i].size();j++)
        {
            if(j==G[i].size()-1||G[i][j]+1!=G[i][j+1])
            {
                T[i].push_back({t++,back,G[i][j]});
                sz[t-1]=G[i][j]-back+1;
                if(j!=G[i].size()-1)back=G[i][j+1];
            }
        }
    }
    for(i=1;T[i].size();i++)
    {
        p=0;q=0;
        while(p<T[i-1].size()&&q<T[i].size())
        {
            if(T[i-1][p].e<T[i][q].s||T[i][q].e<T[i-1][p].s)
            {

            }
            else
            {
                E[T[i-1][p].num].push_back(T[i][q].num);
                E[T[i][q].num].push_back(T[i-1][p].num);
            }
            if(T[i-1][p].e<T[i][q].e)p++;
            else q++;
        }
    }
    dfs(0,-1);
}
int DistanceSum (int N, int *X, int *Y)
{
    a=N;
    xx=2147483647;yy=2147483647;
    for(i=1;i<=a;i++)x[i]=X[i-1],y[i]=Y[i-1];
    for(i=1;i<=a;i++)xx=std::min(xx,x[i]),yy=std::min(yy,y[i]);
    for(i=1;i<=a;i++)x[i]-=xx,y[i]-=yy;
    f();
    for(i=1;i<=a;i++)t=x[i],x[i]=y[i],y[i]=t;
    f();
    return sum%mod;
}

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