Submission #448000

#	Time	Username	Problem	Language	Result	Execution time	Memory
448000		dxz05	Ideal city (IOI12_city)	C++14	32 / 100	1094 ms	7368 KiB

city

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9;
const int MAXN = 2e5 + 3e2;

vector<int> g[MAXN];

vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};

int DistanceSum(int N, int *X, int *Y) {
    map<pair<int, int>, int> mp;
    for (int i = 0; i < N; i++){
        mp[{X[i], Y[i]}] = i;
    }

    for (int i = 0; i < N; i++){
        for (int j = 0; j < 4; j++){
            if (mp.find({X[i] + dx[j], Y[i] + dy[j]}) != mp.end()){
                g[i].push_back(mp[{X[i] + dx[j], Y[i] + dy[j]}]);
            }
        }
    }

    ll ans = 0;

    for (int i = 0; i < N; i++){
        queue<int> q;
        q.push(i);

        vector<int> d(N, 1e9);
        d[i] = 0;

        while (!q.empty()){
            int x = q.front(); q.pop();
            ans += d[x];

            for (int y : g[x]){
                if (d[y] == 1e9){
                    d[y] = d[x] + 1;
                    q.push(y);
                }
            }
        }

    }

    ans >>= 1;

    return ans % MOD;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45