| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 417405 | Collypso | 이상적인 도시 (IOI12_city) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
vt<vt<int>> tree;
map<pii, int> vertix;
int cur_vertix;
void dfs1(pii v, int cur)
{
vertix[v] = cur;
int u2 = vertix[{v.F, v.S + 1}];
if (u2 == 1) dfs1({v.F, v.S + 1}, cur);
int u3 = vertix[{v.F, v.S - 1}];
if (u3 == 1) dfs1({v.F, v.S - 1}, cur);
int u1 = vertix[{v.F + 1, v.S}];
if (u1 > 1) tree[cur].pb(u1), tree[u1].pb(cur);
else if (u1 == 1)
{
cur_vertix++, tree[cur].pb(cur_vertix), tree[cur_vertix].pb(cur);
dfs1({v.F + 1, v.S}, cur_vertix);
}
}
vt<int> vertix_val, subtree_sum, used1, used2;
void dfs2(int v)
{
used1[v] = 1;
subtree_sum[v] = vertix_val[v];
for(int to : tree[v])
{
if (used1[to]) continue;
dfs2(to);
subtree_sum[v] += subtree_sum[to];
}
}
void dfs3(int v, ll& ans)
{
used2[v] = 1;
for(int to : tree[v])
{
if (used2[to]) continue;
ans = (ans + (subtree_sum[to] * (subtree_sum[2] - subtree_sum[to])) % MOD) % MOD;
dfs3(to, ans);
}
}
ll Calc(int N, vt<pii> sorted)
{
vertix.clear(), tree.clear(), vertix_val.clear(), subtree_sum.clear();
used1.clear(), used2.clear();
sort(all(sorted));
for(int i = 0; i < N; i++) vertix[sorted[i]] = 1;
cur_vertix = 1, tree.resize(N);
for(int i = 0; i < N; i++)
if (vertix[sorted[i]] == 1)
cur_vertix++, dfs1(sorted[i], cur_vertix);
vertix_val.resize(cur_vertix + 1);
for(auto& x : vertix) vertix_val[x.S]++;
subtree_sum.resize(cur_vertix + 1);
used1.resize(cur_vertix + 1), used2.resize(cur_vertix + 1);
ll ans = 0;
dfs2(2), dfs3(2, ans);
return ans;
}
int DistanceSum(int N, int* X, int* Y)
{
vt<pii> x, y;
for(int i = 0; i < N; i++) x.pb({X[i], Y[i]}), y.pb({Y[i], X[i]});
return (Calc(N, x) + Calc(N, y)) % MOD;
}