| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 415036 | Collypso | Ideal city (IOI12_city) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
/**
main()
{
//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tmp;
/* Set input and output buffering */
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, i;
tmp = scanf("%d", &N);
assert(tmp == 1);
int *sq_x, *sq_y;
sq_x = (int*) malloc(N * sizeof(int));
sq_y = (int*) malloc(N * sizeof(int));
for (i = 0; i < N; i++) {
tmp = scanf("%d %d", &sq_x[i], &sq_y[i]);
assert(tmp == 2);
}
int ds = DistanceSum(N, sq_x, sq_y);
printf("%d\n", ds);
}
/**/
/*
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
*/