oj.uz

Submission #767874

# Submission time Handle Problem Language Result Execution time Memory
767874 2023-06-27T08:50:14 Z boris_mihov Ideal city (IOI12_city) C++17
0 / 100
 1000 ms 9024 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 5224 KB Output is correct
2 Correct 841 ms 5204 KB Output is correct
3 Execution timed out 1080 ms 9024 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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