제출 #415000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415000		snasibov05	Ideal city (IOI12_city)	C++14	0 / 100	15 ms	4556 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]);
            }
        }
    }

    ll res = 0;
    ll k = distsum(v[1][1], ed);
    res += k;

    for (int i = 1; i <= mx_x; ++i) {
        ll cur = k + (i-1) * mx_y * 1ll;
        for (int j = 1; j <= mx_y; ++j) {
            if (i == 1 && j == 1) continue;
            cur += mx_x * 1ll;
            res += cur - (mx_y - j + 1) * mx_x * 1ll;
        }
    }

    res /= 2ll;

    return res % m;

}

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