oj.uz

Submission #7579

# Submission time Handle Problem Language Result Execution time Memory
7579 2014-08-11T12:53:14 Z baneling100 Ideal city (IOI12_city) C++
32 / 100
 40 ms 18760 KB 
#include <algorithm>
#include <vector>
#include <map>

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, Ans, GroupNum[1000000], GroupSize[1000000], Check[1000000];

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]);
            }
    }
}

void TreeDP(void)
{
}

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+=Sum*(N-Sum);
    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 4 ms 16180 KB Output is correct
3 Correct 0 ms 16312 KB Output is correct
4 Correct 0 ms 16312 KB Output is correct
5 Correct 0 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 0 ms 16316 KB Output is correct
9 Correct 0 ms 16316 KB Output is correct
10 Correct 4 ms 16316 KB Output is correct

Subtask #3
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 17572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 18760 KB Output isn't correct
2 Halted 0 ms 0 KB -