oj.uz

Submission #31106

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

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

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 17992 KB Output is correct
2 Correct 953 ms 17992 KB Output is correct
3 Correct 739 ms 17992 KB Output is correct
4 Execution timed out 1000 ms 17992 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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