Submission #31111

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

city

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e17;
const int mod=1000000000;
 
int n, dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
ll d[2010][2010];
vector<int> v[2010];
map<pair<int, int>, ll> M;
map<pair<int, int>, ll> 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);
                    }
                }
            }
        }
        ll 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], ans%=mod;
        }
        return (int)((ans/2)%mod);
    }
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int)':
city.cpp:14: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:45:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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