Submission #31106

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

city

#include<bits/stdc++.h>
using namespace std;
const int INF=1987654321;
 
int n, d[2010][2010], dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
vector<int> v[2010];
map<pair<int, int>, int> M;
map<pair<int, int>, int> sum;
 
void dfs(int x, int st){
    for(int i=0; i<v[x].size(); i++){
        int u=v[x][i];
        if(d[st][u]>d[st][x]+1){
            d[st][u]=d[st][x]+1;
            dfs(u, st);
        }
    }
}
 
int DistanceSum(int N, int *X, int *Y) {
    n=N;
    if(n<=2000){
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int k=0; k<4; k++){
                    if(X[i]+dx[k]==X[j]&&Y[i]+dy[k]==Y[j]){
                        v[i].push_back(j);
                        v[j].push_back(i);
                    }
                }
            }
        }
        int ans=0;
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) d[i][j]=INF;
        for(int i=0; i<n; i++){
            d[i][i]=0;
            dfs(i, i);
            for(int j=0; j<n; j++) ans+=d[i][j];
        }
        return ans/2;
    }
    int x1=INF, x2=0, y1=INF, y2=0;
    for(int i=0; i<n; i++){
        x1=min(x1, X[i]), x2=max(x2, X[i]);
        y1=min(y1, Y[i]), y2=max(y2, Y[i]);
    }
    M[make_pair(0, 0)]=0;
    for(int i=0; i<=x2-x1; i++){
        for(int j=0; j<=y2-y1; j++){
            M[make_pair(i+1, j)]=M[make_pair(i, j)]+1;
            M[make_pair(i, j+1)]=M[make_pair(i, j)]+1;
        }
    }
    for(int i=0; i<=x2-x1; i++){
        for(int j=0; j<=y2-y1; j++){
            sum[make_pair(i, j)]=M[make_pair(i, j)];
            if(i!=0) sum[make_pair(i, j)]+=sum[make_pair(i-1, j)];
            if(j!=0) sum[make_pair(i, j)]+=sum[make_pair(i, j-1)];
            if(i!=0&&j!=0) sum[make_pair(i, j)]-=sum[make_pair(i-1, j-1)];
        }
    }
    int ans=0;
    for(int i=0; i<n; i++){
        int x=X[i], y=Y[i], num=ans;
//        printf("%d %d %d %d\n", x-x1, x2-x, y2-y, y-y1);
        ans+=sum[make_pair(x2-x, y2-y)];
        ans+=sum[make_pair(x-x1, y-y1)];
        ans+=sum[make_pair(x-x1, y2-y)];
        ans+=sum[make_pair(x2-x, y-y1)];
        ans-=sum[make_pair(0, y-y1)];
        ans-=sum[make_pair(0, y2-y)];
        ans-=sum[make_pair(0, x2-x)];
        ans-=sum[make_pair(0, x-x1)];
    }
    return ans/2;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int)':
city.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++){
                   ^
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:64:29: warning: unused variable 'num' [-Wunused-variable]
         int x=X[i], y=Y[i], num=ans;
                             ^

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