oj.uz

Submission #38833

# Submission time Handle Problem Language Result Execution time Memory
38833 2018-01-07T05:05:28 Z andy627 Ideal city (IOI12_city) C++14
32 / 100
 153 ms 2320 KB 
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#define ff first
#define ss second
#define LL long long
#define pll pair<LL,LL>
#define MOD 1000000000
using namespace std;

struct ci{
    LL x,y;
    int nea[4]={-1,-1,-1,-1};
}inf[2222];

LL n,sum;
LL x[2222],y[2222];
map<pll,int> mp;

queue<int> qi,qd;
bool is_gone[2222];

int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};

void bfs(int v,int d){
    qi.push(v);
    qd.push(d);
    is_gone[v]=1;
    while(!qi.empty()){
        int pi=qi.front(); qi.pop();
        int pd=qd.front(); qd.pop();
        sum=(sum+pd)%(MOD*2);

        for(int i=0;i<4;i++){
            if(inf[pi].nea[i]!=-1 && !is_gone[inf[pi].nea[i]]){
                qi.push(inf[pi].nea[i]);
                qd.push(pd+1);
                is_gone[inf[pi].nea[i]]=1;
            }
        }
    }
}

int DistanceSum(int N,int *X,int *Y){
    n=N;
    for(int i=0;i<N;i++) x[i]=X[i];
    for(int i=0;i<N;i++) y[i]=Y[i];

    for(int i=0;i<n;i++) mp.insert({{x[i],y[i]},i});
    for(int i=0;i<n;i++){
        inf[i].x=x[i];
        inf[i].y=y[i];
        for(int j=0;j<4;j++){
            int nx=x[i]+dx[j];
            int ny=y[i]+dy[j];

            map<pll,int>::iterator it=mp.find({nx,ny});
            if(it!=mp.end()) inf[i].nea[j]=it->ss;
        }
    }

    if(n<=2000){
        /*
        for(int i=0;i<n;i++){
            printf("%2d %2d ",inf[i].x,inf[i].y);
            for(int j=0;j<4;j++) printf("%2d ",inf[i].nea[j]);
            printf("\n");
        }
        printf("\n");
        */
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) is_gone[j]=0;
            bfs(i,0);
        }

        return sum/2;
    }

    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2308 KB Output is correct
2 Correct 26 ms 2308 KB Output is correct
3 Correct 76 ms 2308 KB Output is correct
4 Correct 63 ms 2308 KB Output is correct
5 Correct 149 ms 2308 KB Output is correct
6 Correct 89 ms 2308 KB Output is correct
7 Correct 153 ms 2308 KB Output is correct
8 Correct 106 ms 2308 KB Output is correct
9 Correct 86 ms 2308 KB Output is correct
10 Correct 83 ms 2308 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -