oj.uz

Submission #869391

# Submission time Handle Problem Language Result Execution time Memory
869391 2023-11-04T09:05:51 Z salmon Ideal city (IOI12_city) C++14
0 / 100
 1000 ms 5528 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adjlst[2100];
set<pair<int,int>> sat;
int d[2100];
map<pair<int,int>,int> mep;

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

    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() && (*it).first == x - 1 && (*it).second == y){
            adjlst[i].push_back(mep[make_pair(x-1,y)]);
        }

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

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

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

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

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

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

    long long 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();

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

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

    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1031 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 5464 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 16 ms 5528 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -