Submission #414986

#	Time	Username	Problem	Language	Result	Execution time	Memory
414986		snasibov05	Ideal city (IOI12_city)	C++14	32 / 100	126 ms	262148 KiB

city

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define oo 1000000000
#define ll long long
#define pb push_back

const int m = 1e9;

int distsum(int v, vector<vector<int>>& ed){
    int n = ed.size();
    vector<int> d(n);
    vector<bool> visited(n);

    queue<int> q;
    q.push(v);
    d[v] = 0;
    visited[v] = true;

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

        for (auto x : ed[cur]){
            if (visited[x]) continue;
            visited[x] = true;
            d[x] = d[cur] + 1;
            q.push(x);
        }
    }

    int res = 0;
    for (int i = 0; i < n; ++i) {
        res += d[i];
    }

    return res;
}

int DistanceSum(int n, int *x, int *y) {

    int mn_x = oo, mn_y = oo;
    for (int i = 0; i < n; ++i) {
        mn_x = min(mn_x, x[i]);
        mn_y = min(mn_y, y[i]);
    }

    for (int i = 0; i < n; ++i) {
        x[i] = x[i] - mn_x + 1;
        y[i] = y[i] - mn_y + 1;
    }

    vector<vector<int>> v(n+1, vector<int>(n+1, -1));

    for (int i = 0; i < n; ++i) {
        v[x[i]][y[i]] = i;
    }

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

    vector<vector<int>> ed(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            int cur_x = x[i] + dx[j];
            int cur_y = y[i] + dy[j];
            if (v[cur_x][cur_y] != -1){
                ed[i].pb(v[cur_x][cur_y]);
            }
        }
    }

    ll res = 0;
    for (int i = 0; i < n; ++i) {
        res += distsum(i, ed) * 1ll;
    }

    res /= 2ll;

    return res % m;

}

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