Submission #415014

#	Time	Username	Problem	Language	Result	Execution time	Memory
415014		snasibov05	Ideal city (IOI12_city)	C++14	0 / 100	14 ms	2252 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]);
    }

    int mx_x = 0, mx_y = 0;

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

    vector<vector<int>> v(mx_x+5, vector<int>(mx_y + 5, -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]);
            }
        }
    }

    vector<int> l(mx_y+2), d(mx_x+2);

    for (int i = 1; i <= mx_y; ++i) {
        int cur = 0;
        for (int j = 1; j <= mx_x; ++j) {
            if (v[j][i] != -1) cur++;
        }
        l[i+1] = l[i] + cur;
    }

    for (int i = 1; i <= mx_x; ++i) {
        int cur = 0;
        for (int j = 1; j <= mx_y; ++j) {
            if (v[i][j] != -1) cur++;
        }
        d[i+1] = d[i] + cur;
    }

    ll k = distsum(0, ed);
    int stx = x[0];
    int sty = y[0];

    ll res = 0;

    for (int i = 0; i < n; ++i) {
        int a = x[i] - stx;
        int b = y[i] - sty;
        ll cur = k;
        cur += a * l[x[i]];
        cur += b * d[y[i]];
        cur -= a * (n - l[x[i]]);
        cur -= b * (n - d[y[i]]);
        res += cur;
    }
    
    res /= 2;

    return res % m;

}

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