Submission #767874

#	Time	Username	Problem	Language	Result	Execution time	Memory
767874		boris_mihov	Ideal city (IOI12_city)	C++17	0 / 100	1080 ms	9024 KiB

city

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <map>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1'000'000'000;

int n;
llong ans;
int cnt[MAXN];
int degree[MAXN];
bool isActive[MAXN];
int x[MAXN], y[MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
std::map <std::pair <int,int>, int> map;
std::vector <int> g[MAXN];
std::queue <int> q;
int cntActive;

int DistanceSum(int N, int *X, int *Y) 
{
    n = N;
    cntActive = n;
    for (int i = 1 ; i <= n ; ++i)
    {
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
        map[{x[i], y[i]}] = i;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (const auto &[dx, dy] : delta)
        {
            if (map.count({x[i] + dx, y[i] + dy}))
            {
                g[i].push_back(map[{x[i] + dx, y[i] + dy}]);
                degree[i]++;
            }
        }
    }

    std::fill(isActive + 1, isActive + 1 + n, true);
    std::fill(cnt + 1, cnt + 1 + n, 1);
    for (int i = 1 ; i <= n ; ++i)
    {
        if (degree[i] == 1)
        {
            q.push(i);
        }
    }

    while (!q.empty() && cntActive > 1)
    {
        int top = q.front();
        ans += 1LL * cnt[top] * (n - cnt[top]);
        isActive[top] = false;
        cntActive--;
        q.pop();

        for (const int &u : g[top])
        {
            if (!isActive[u])
            {
                continue;
            }
            
            degree[u]--;
            cnt[u] += cnt[top];
            if (degree[u] == 1)
            {
                isActive[u] = false;
                q.push(u);
            }
        }
    }
    
    ans %= MOD;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (isActive[i] && isActive[j])
            {
                ans += (1LL * (cnt[i] * cnt[j]) % MOD) * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
                ans %= MOD;
            }            
        }
    }

    return ans;
}

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