oj.uz

Submission #869410

# Submission time Handle Problem Language Result Execution time Memory
869410 2023-11-04T09:21:38 Z salmon Ideal city (IOI12_city) C++14
32 / 100
 82 ms 5468 KB 
#include <bits/stdc++.h>
using namespace std;


int DistanceSum(int N, int *X, int *Y) {

    vector<int> adjlst[2100];
    set<pair<int,int>> sat;
    int d[2100];
    map<pair<int,int>,int> mep;

    for(int i = 0; i < N; i++){
        mep[make_pair(X[i],Y[i])] = i;
        sat.insert(make_pair(X[i],Y[i]));
    }

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

        auto it = sat.find(make_pair(x - 1,y));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x-1,y)]);
        }

        it = sat.find(make_pair(x + 1,y));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x+1,y)]);
        }

        it = sat.find(make_pair(x,y - 1));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x,y - 1)]);
        }

        it = sat.find(make_pair(x,y + 1));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x,y + 1)]);
        }
    }

    int ans = 0;

    for(int i = 0; i < N; i++){
        for(int i = 0; i < N; i++){
            d[i] = -1;
        }

        queue<int> q;

        q.push(i);
        d[i] = 0;

        while(!q.empty()){
            int j = q.front();
            q.pop();

            for(int k : adjlst[j]){
                if(d[k] == -1){
                    d[k] = d[j] + 1;
                    q.push(k);
                }
            }
        }

        for(int i = 0; i < N; i++){
            ans += d[i];
            ans %= 1000000000;
        }
    }

    return ans/2;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 18 ms 652 KB Output is correct
3 Correct 42 ms 724 KB Output is correct
4 Correct 43 ms 604 KB Output is correct
5 Correct 77 ms 604 KB Output is correct
6 Correct 64 ms 788 KB Output is correct
7 Correct 82 ms 792 KB Output is correct
8 Correct 69 ms 600 KB Output is correct
9 Correct 64 ms 604 KB Output is correct
10 Correct 58 ms 604 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 5468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 5468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -