Submission #429949

#	Time	Username	Problem	Language	Result	Execution time	Memory
429949		JeanBombeur	Ideal city (IOI12_city)	C++17	32 / 100	627 ms	1228 KiB

city

#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <algorithm>
using namespace std;

const long long MOD = (1000 * 1000 * 1000);
const int MAX_POINTS = (100 * 1000);

struct info {
    int lig, col;
    long long dist;
};

int Dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

unordered_map <long long, int> Points;

info File[MAX_POINTS];
int deb = 0, fin = 0;

long long Hash(int lig, int col) {
    return ((long long)lig << 32) + (long long)col;
}

void Add(info cur) {
    for (int i = 0; i < 4; i ++)
    {
        int nvLig = cur.lig + Dir[i][0], nvCol = cur.col + Dir[i][1];
        if (Points[Hash(nvLig, nvCol)] -- > 0)
            File[fin ++] = {nvLig, nvCol, cur.dist + 1};
    }
    return;
}

long long Bfs(info dep) {
    Points[Hash(dep.lig, dep.col)] --;
    deb = 0, fin = 0;
    File[fin ++] = dep;
    long long ans = 0;
    while (deb < fin)
    {
        // printf("%lld ", File[deb].dist);
        ans += File[deb].dist;
        Add(File[deb ++]);
    }
    for (int i = 0; i < fin; i ++)
    {
        Points[Hash(File[i].lig, File[i].col)] = 1;
    }
    return ans % MOD;
}

int DistanceSum(int nbPoints, int *X, int *Y) {

    long long sumX = 0, sumY = 0;
    
    for (int i = 0; i < nbPoints; i ++)
    {
        Points[Hash(X[i], Y[i])] ++;
        sumX += X[i], sumY += Y[i];
    }
    
    long long ans = 0;
    
    if (nbPoints <= 2000)
    {
        for (int i = 0; i < nbPoints; i ++)
        {
            ans += Bfs({X[i], Y[i], 0LL});
            // printf("%lld ", ans);
        }
        ans %= MOD;
        return ans / 2;
    }
    return 0;
    
    sort(X, X + nbPoints);
    sort(Y, Y + nbPoints);
    
    for (int i = 0; i < nbPoints; i ++)
    {
        ans += sumX - (nbPoints - i) * X[i];
        sumX -= X[i];
        ans += sumY - (nbPoints - i) * Y[i];
        sumY -= Y[i];
        ans %= MOD;
    }
    
    return ans;
}

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