제출 #158240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158240		davitmarg	이상적인 도시 (IOI12_city)	C++17	0 / 100	8 ms	3068 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] = 1;
    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);
    }
    else
    {
        int mnX, mnY, mxX, mxY;
        mnY = mnX = mod;
        mxY = mxX = 0;
        for (int i = 1; i <= n; i++)
        {
            mnX = min(mnX, x[i]);
            mxX = max(mxX, x[i]);
            mnY = min(mnY, y[i]);
            mxY = max(mxY, y[i]);
        }
        for (int i = mxX; i <= mxX; i++)
        {
            ans += i - 1;
            ans %= mod;
        }
        for (int i = mxY; i <= mxY; i++)
        {
            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

/*




*/

컴파일 시 표준 에러 (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: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45