oj.uz

Submission #31111

# Submission time Handle Problem Language Result Execution time Memory
31111 2017-08-10T01:47:19 Z h0ngjun7 Ideal city (IOI12_city) C++14
11 / 100
 1000 ms 33908 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33764 KB Output is correct
2 Correct 0 ms 33764 KB Output is correct
3 Correct 0 ms 33764 KB Output is correct
4 Correct 0 ms 33764 KB Output is correct
5 Correct 0 ms 33764 KB Output is correct
6 Correct 3 ms 33764 KB Output is correct
7 Correct 16 ms 33764 KB Output is correct
8 Correct 0 ms 33764 KB Output is correct
9 Correct 13 ms 33764 KB Output is correct
10 Correct 23 ms 33764 KB Output is correct
11 Correct 23 ms 33764 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 33764 KB Output is correct
2 Execution timed out 1000 ms 33764 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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