Submission #256413

#	Time	Username	Problem	Language	Result	Execution time	Memory
256413		Akashi	Ideal city (IOI12_city)	C++14	32 / 100	132 ms	768 KiB

city

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

const int DIM = 1e5 + 5;
const int MOD = 1e9 + 7;

int n;
vector <int> v[5000];

int bfs(int nod) {

    queue <int> q;
    vector <bool> viz(n, 0);
    vector <int> dist(n, 0);

    q.push(nod);
    viz[nod] = 1;

    int ans = 0;
    while (!q.empty()) {
        int nod = q.front();
        q.pop();
        ans = ans + dist[nod];
        for (auto it : v[nod]) {
            if (!viz[it]) {
                viz[it] = 1;
                dist[it] = dist[nod] + 1;
                q.push(it);
            }
        }
    }

    return ans;
}

int DistanceSum(int _n, int *X, int *Y) {
    n = _n;
    if (n <= 5000) {
        for (int i = 0; i < n ; ++i) {
            for (int j = i; j < n ; ++j) {
                if ((X[i] == X[j] && abs(Y[i] - Y[j]) == 1) || (Y[i] == Y[j] && abs(X[i] - X[j]) == 1)) {
                    v[i].push_back(j);
                    v[j].push_back(i);
                }
            }
        }

        long long sol = 0;
        for (int i = 0; i < n ; ++i) sol += bfs(i);

        sol = sol / 2;
        sol %= MOD;
        return sol;
    }


    return n;
}

/**
    11
    2 5
    2 6
    3 3
    3 6
    4 3
    4 4
    4 5
    4 6
    5 3
    5 4
    5 6
**/

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