Submission #7580

#	Time	Username	Problem	Language	Result	Execution time	Memory
7580		baneling100	Ideal city (IOI12_city)	C++98	100 / 100	276 ms	29408 KiB

city

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