제출 #158256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158256		davitmarg	이상적인 도시 (IOI12_city)	C++17	55 / 100	158 ms	6384 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], n;
vector<int> g[100005];

LL ans;

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;

        LL pr;

        pr = 0;
        v.clear();
        for (int i = 1; i <= n; i++)
            v.PB(MP(x[i], y[i]));
        sort(all(v));

        for (int i = 0; i < v.size(); i++)
        {
            if (i == 0 || v[i].first != v[i - 1].first)
                pr += i;
            //cout << pr << " : " << v[i].first << "\n";
            ans += pr;
            ans %= mod;
        }

        pr = 0;
        v.clear();
        for (int i = 1; i <= n; i++)
            v.PB(MP(y[i], x[i]));
        sort(all(v));

        for (int i = 0; i < v.size(); i++)
        {
            if (i == 0 || v[i].first != v[i - 1].first)
                pr += i;
            ans += pr;
            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

/*

4
1 1
1 2
1 3
2 3

  #
###

##
#
#

0 

*/

컴파일 시 표준 에러 (stderr) 메시지

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

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