oj.uz

Submission #429683

# Submission time Handle Problem Language Result Execution time Memory
429683 2021-06-16T08:41:32 Z someone Ideal city (IOI12_city) C++14
55 / 100
 182 ms 36684 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 5 ms 5452 KB Output is correct
6 Correct 6 ms 6092 KB Output is correct
7 Correct 6 ms 6164 KB Output is correct
8 Correct 5 ms 6092 KB Output is correct
9 Correct 6 ms 6164 KB Output is correct
10 Correct 6 ms 6092 KB Output is correct
11 Correct 5 ms 6092 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16844 KB Output is correct
2 Correct 45 ms 16844 KB Output is correct
3 Correct 96 ms 28620 KB Output is correct
4 Correct 100 ms 28748 KB Output is correct
5 Correct 163 ms 36548 KB Output is correct
6 Correct 171 ms 36556 KB Output is correct
7 Correct 169 ms 36556 KB Output is correct
8 Correct 172 ms 36672 KB Output is correct
9 Correct 182 ms 36684 KB Output is correct
10 Correct 168 ms 36556 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10188 KB Output is correct
2 Correct 16 ms 10252 KB Output is correct
3 Correct 23 ms 10864 KB Output is correct
4 Correct 22 ms 10848 KB Output is correct
5 Correct 34 ms 12100 KB Output is correct
6 Correct 32 ms 12108 KB Output is correct
7 Correct 40 ms 12064 KB Output is correct
8 Correct 34 ms 12100 KB Output is correct
9 Correct 32 ms 12108 KB Output is correct
10 Correct 33 ms 12012 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 10188 KB Output isn't correct
2 Halted 0 ms 0 KB -