oj.uz

Submission #18847

# Submission time Handle Problem Language Result Execution time Memory
18847 2016-02-16T00:55:26 Z ggoh Ideal city (IOI12_city) C++
100 / 100
 51 ms 15584 KB 
#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.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10144 KB Output is correct
2 Correct 6 ms 10276 KB Output is correct
3 Correct 20 ms 10592 KB Output is correct
4 Correct 21 ms 10856 KB Output is correct
5 Correct 36 ms 11380 KB Output is correct
6 Correct 36 ms 12044 KB Output is correct
7 Correct 37 ms 11776 KB Output is correct
8 Correct 24 ms 11380 KB Output is correct
9 Correct 31 ms 11964 KB Output is correct
10 Correct 45 ms 15584 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10672 KB Output is correct
2 Correct 7 ms 10540 KB Output is correct
3 Correct 28 ms 11780 KB Output is correct
4 Correct 22 ms 11384 KB Output is correct
5 Correct 43 ms 13756 KB Output is correct
6 Correct 45 ms 12224 KB Output is correct
7 Correct 51 ms 13528 KB Output is correct
8 Correct 42 ms 12568 KB Output is correct
9 Correct 38 ms 11908 KB Output is correct
10 Correct 39 ms 12040 KB Output is correct