Submission #31109

#	Time	Username	Problem	Language	Result	Execution time	Memory
31109		h0ngjun7	Ideal city (IOI12_city)	C++14	11 / 100	1000 ms	40880 KiB

city

#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int i,j,k;
unordered_map<long long,int>um;
long long dist[2222][2222],ans;
long long f(int x,int y)
{
    return (long long)y+((long long)x<<31);
}
int DistanceSum(int n, int *x, int *y) {
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            dist[i][j]=4294967296ll;
    for(i=0;i<n;i++)
    {
        um[f(x[i],y[i])]=i+1;
        for(j=0;j<4;j++)
        {
            if(um[f(x[i]+dx[j],y[i]+dy[j])])
            {
                dist[i+1][um[f(x[i]+dx[j],y[i]+dy[j])]]=1;
                dist[um[f(x[i]+dx[j],y[i]+dy[j])]][i+1]=1;
            }
        }
    }
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                //printf("dist[%d][%d]=%d\n",i,j,dist[i][j]);
                ans+=dist[i][j];
            }
    return (ans/2)%1000000000;
}

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