Submission #158242

#	Time	Username	Problem	Language	Result	Execution time	Memory
158242		davitmarg	Ideal city (IOI12_city)	C++17	32 / 100	161 ms	3448 KiB

city

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000000ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

int x[100005], y[100005], used[100005], d[100005], ans, n;
vector<int> g[100005];

void bfs(int v)
{
    for (int i = 1; i <= n; i++)
        used[i] = 0;
    queue<int> q;
    used[v] = 1;
    d[v] = 0;
    q.push(v);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        ans += d[v];
        ans %= mod;
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (used[to])
                continue;
            d[to] = d[v] + 1;
            used[to] = 1;
            q.push(to);
        }
    }
}

int DistanceSum(int N, int *X, int *Y)
{
    n = N;
    for (int i = 1; i <= n; i++)
    {
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
    }
    if (n <= 2000)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1)
                    g[i].PB(j);
        for (int i = 1; i <= n; i++)
            bfs(i);
        ans /= 2;
    }
    else
    {
        vector<pair<int, int>> v;

        v.clear();
        for (int i = 1; i <= n; i++)
            v.PB(MP(x[i], y[i]));
        sort(all(v));
        for (int i = 1; i <= n; i++)
            if (i == 1 || v[i].first != v[i - 1].first)
            {
                ans += i - 1;
                ans %= mod;
            }

        v.clear();
        for (int i = 1; i <= n; i++)
            v.PB(MP(y[i], x[i]));
        sort(all(v));
        for (int i = 1; i <= n; i++)
            if (i == 1 || v[i].first != v[i - 1].first)
            {
                ans += i - 1;
                ans %= mod;
            }
    }

    return ans;
}

#ifdef death

int main()
{
    int N, X[102], Y[102];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> X[i] >> Y[i];
    cout << DistanceSum(N, X, Y) << endl;
    return 0;
}

#endif

/*




*/

Compilation message (stderr)

city.cpp: In function 'void bfs(int)':
city.cpp:42:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~

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