제출 #415038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415038		Collypso	이상적인 도시 (IOI12_city)	C++17	11 / 100	1096 ms	4192 KiB

city

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

const int MOD = 1e9;

using namespace std;

map<pii, int> filled;
map<pii, int> dist;

int bfs(pii start, int i)
{
    dist.clear();
    for(auto x : filled)
        if (x.S) dist[x.F] = INT_MAX;
    queue<pii> q;
    q.push(start);
    dist[start] = 0;
    while(!q.empty())
    {
        pii v = q.front();
        q.pop();

        int d = dist[{v.F, v.S}];
        if (filled[{v.F + 1, v.S}])
        {
            if (dist[{v.F + 1, v.S}] > d + 1)
                q.push({v.F + 1, v.S}), dist[{v.F + 1, v.S}] = d + 1;
        }
        if (filled[{v.F, v.S + 1}])
        {
            if (dist[{v.F, v.S + 1}] > d + 1)
                q.push({v.F, v.S + 1}), dist[{v.F, v.S + 1}] = d + 1;
        }
        if (filled[{v.F - 1, v.S}])
        {
            if (dist[{v.F - 1, v.S}] > d + 1)
                q.push({v.F - 1, v.S}), dist[{v.F - 1, v.S}] = d + 1;
        }
        if (filled[{v.F, v.S - 1}])
        {
            if (dist[{v.F, v.S - 1}] > d + 1)
                q.push({v.F, v.S - 1}), dist[{v.F, v.S - 1}] = d + 1;
        }
    }
    int ans = 0;
    for(auto x : dist)
    {
        if (filled[x.F] > i) ans = (1ll * ans + x.S) % MOD;
    }
    return ans;
}

int subtask12(int N, int* X, int* Y)
{
    for(int i = 0; i < N; i++)
        filled[{*(X + i), *(Y + i)}] = i + 1;
    int ans = 0;
    for(int i = 0; i < N; i++)
        ans = (1ll * ans + bfs({*(X + i), *(Y + i)}, i + 1)) % MOD;
    return ans;
}

int DistanceSum(int N, int* X, int* Y)
{
    if (N <= 2000) return subtask12(N, X, Y);

}

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

20
3 5
4 6
2 5
3 4
6 5
1 6
2 7
3 1
2 6
1 5
5 5
5 4
4 7
4 2
3 2
3 3
4 4
4 3
4 5
5 2

*/

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

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^

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