Submission #429683

#	Time	Username	Problem	Language	Result	Execution time	Memory
429683		someone	Ideal city (IOI12_city)	C++14	55 / 100	182 ms	36684 KiB

city

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 2e5 + 42, M = 2e3 + 10, INF = 1e10, MOD = 1e9;

vector<int> adj[N];
ll n, x[N], y[N], id[M][M], dist[M], occ[N], sumX[N], cumOcc[N];

ll dl[] = {0, 0, 1, -1},
    dc[] = {1, -1, 0, 0};

void BFS(int i) {
    for(int j = 0; j < n; j++)
        dist[j] = INF;
    dist[i] = 0;
    queue<int> q;
    q.push(i);
    while(!q.empty()) {
        int j = q.front();
        q.pop();

        for(int k : adj[j]) {
            if(dist[k] == INF) {
                dist[k] = dist[j] + 1;
                q.push(k);
            }
        }
    }
}

int getSumX() {
    for(int i = 0; i < N; i++)
        occ[i] = cumOcc[i] = sumX[i] = 0;
    for(int i = 0; i < n; i++)
        occ[x[i]]++;
    for(int i = 1; i < N; i++)
        cumOcc[i] = (cumOcc[i-1] + occ[i-1]) % MOD;
    for(int i = 1; i < N; i++)
        sumX[i] = (sumX[i-1] + occ[i-1] * (i-1)) % MOD;
    ll diffX = 0;
    for(int i = 0; i < n; i++) {
        //cout << i << ' ' << occ[i] << ' ' << cumOcc[i] << ' ' << sumX[i] << ' ' << (occ[i] * ((cumOcc[i] * i - sumX[i] + MOD) % MOD)) << '\n';
        diffX = (diffX + (occ[i] * ((cumOcc[i] * i - sumX[i] + MOD) % MOD))) % MOD;
        //cout << diffX << '\n';
    }
    return diffX;
}

signed DistanceSum(int n1, int *X, int *Y) {
    n = n1;
    ll minx = INF, miny = INF;
    for(int i = 0; i < n; i++) {
        x[i] = X[i];
        y[i] = Y[i];
        minx = min(minx, x[i]);
        miny = min(miny, y[i]);
    }
    for(int i = 0; i < n; i++) {
        x[i] -= minx;
        y[i] -= miny;
    }

    if(n <= 2000) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                id[i][j] = -1;
        for(int i  =0; i < n; i++)
            id[x[i]][y[i]] = i;
        for(int i = 0; i < n; i++) {
            ll l = x[i], c = y[i];
            for(int j = 0; j < 4; j++) {
                ll l2 = l + dl[j], c2 = c + dc[j];
                if(-1 < l2 && l2 < n && -1 < c2 && c2 < n) {
                    if(id[l2][c2] != -1) {
                        adj[i].push_back(id[l2][c2]);
                        adj[id[l2][c2]].push_back(i);
                    }
                }
            }
        }
        ll sum = 0;
        for(int i = 0; i < n; i++) {
            BFS(i);
            ll t = 0;
            for(int j = 0; j < n; j++)
                sum = (dist[j] + sum) % MOD;
            for(int j = 0; j < n; j++)
                t += dist[j];
        }
        return sum/2;
    }

    ll sum = 0;
    sum = getSumX();
    for(int i = 0; i < n; i++)
        swap(x[i], y[i]);
    sum = (sum + getSumX()) % MOD;
    return sum;
}

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