oj.uz

Submission #7580

# Submission time Handle Problem Language Result Execution time Memory
7580 2014-08-11T12:55:01 Z baneling100 Ideal city (IOI12_city) C++
100 / 100
 276 ms 29408 KB 
#include <algorithm>
#include <vector>
#include <map>
#define MOD 1000000000

using namespace std;

typedef pair <int,int> ppair;
map <ppair,int> Map1;
map <ppair,int> Map2;
map <ppair,int> :: iterator it;
vector <int> B[100000];
pair <int,int> A[100000];
int N, M, GroupNum[1000000], GroupSize[1000000], Check[1000000];
long long Ans;

void TheyAreGroup(int Left, int Right)
{
    int i;

    for(i=Left ; i<=Right ; i++)
    {
        Map1.insert(make_pair(make_pair(A[i].first,A[i].second),M));
        GroupNum[i]=M;
    }
    GroupSize[M]=Right-Left+1;
    M++;
}

void MakeGroup(void)
{
    int i, j;

    for(i=0 ; i<M ; i++)
    {
        Check[i]=0;
        B[i].clear();
    }
    M=0;
    Map1.clear();
    Map2.clear();
    for(i=0 ; i<N ; i++)
    {
        for(j=i ; j<N ; j++)
        {
            if(i!=j && (A[j].first!=A[j-1].first || A[j].second!=A[j-1].second+1))
            {
                TheyAreGroup(i,j-1);
                i=j-1;
                break;
            }
        }
        if(j==N)
        {
            TheyAreGroup(i,N-1);
            break;
        }
    }
    for(i=0 ; i<N ; i++)
    {
        it=Map1.find(make_pair(A[i].first+1,A[i].second));
        if(it!=Map1.end())
            if(Map2.find(make_pair(GroupNum[i],it->second))==Map2.end())
            {
                Map2.insert(make_pair(make_pair(GroupNum[i],it->second),0));
                Map2.insert(make_pair(make_pair(it->second,GroupNum[i]),0));
                B[GroupNum[i]].push_back(it->second);
                B[it->second].push_back(GroupNum[i]);
            }
        it=Map1.find(make_pair(A[i].first-1,A[i].second));
        if(it!=Map1.end())
            if(Map2.find(make_pair(GroupNum[i],it->second))==Map2.end())
            {
                Map2.insert(make_pair(make_pair(GroupNum[i],it->second),0));
                Map2.insert(make_pair(make_pair(it->second,GroupNum[i]),0));
                B[GroupNum[i]].push_back(it->second);
                B[it->second].push_back(GroupNum[i]);
            }
    }
}

int TreeDP(int Now)
{
    int i, j=B[Now].size(), Sum=0;

    for(i=0 ; i<j ; i++)
        if(!Check[B[Now][i]])
        {
            Check[B[Now][i]]=1;
            Sum+=TreeDP(B[Now][i]);
        }
    Sum+=GroupSize[Now];
    Ans+=(long long)Sum*((long long)N-(long long)Sum);
    Ans%=MOD;
    return Sum;
}

int DistanceSum(int N_, int *X, int *Y)
{
    int i, temp;

    N=N_;
    for(i=0 ; i<N ; i++)
        A[i]=make_pair(X[i],Y[i]);
    sort(A,A+N);
    MakeGroup();
    Check[0]=1;
    temp=TreeDP(0);
    for(i=0 ; i<N ; i++)
        A[i]=make_pair(Y[i],X[i]);
    sort(A,A+N);
    MakeGroup();
    Check[0]=1;
    temp=TreeDP(0);
    return Ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17572 KB Output is correct
2 Correct 32 ms 17572 KB Output is correct
3 Correct 84 ms 19740 KB Output is correct
4 Correct 84 ms 19872 KB Output is correct
5 Correct 200 ms 23300 KB Output is correct
6 Correct 188 ms 23432 KB Output is correct
7 Correct 220 ms 23432 KB Output is correct
8 Correct 204 ms 23168 KB Output is correct
9 Correct 208 ms 23724 KB Output is correct
10 Correct 240 ms 29404 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 18760 KB Output is correct
2 Correct 40 ms 18232 KB Output is correct
3 Correct 120 ms 22776 KB Output is correct
4 Correct 108 ms 21456 KB Output is correct
5 Correct 260 ms 29240 KB Output is correct
6 Correct 232 ms 25464 KB Output is correct
7 Correct 276 ms 29408 KB Output is correct
8 Correct 256 ms 25676 KB Output is correct
9 Correct 236 ms 25148 KB Output is correct
10 Correct 228 ms 24884 KB Output is correct