이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> PII;
typedef vector <int> VI;
typedef vector <VI> VVI;
const int MOD = (int) 1e9;
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
int dfs(int nod, int par, VVI &g, VI &w, VI &lvl, VI &sp) {
lvl[nod] = lvl[par] + 1, sp[nod] = 0;
int ans = 0;
for(auto it : g[nod]) {
if(lvl[it] == 0) {
ans += dfs(it, nod, g, w, lvl, sp);
sp[nod] += sp[it];
mod(sp[nod]);
}
}
ans = (ans + 2LL * w[nod] * sp[nod] * lvl[nod]) % MOD;
for(auto it : g[nod]) {
if(lvl[it] == lvl[nod] + 1) {
ans = (ans + 1LL * (sp[nod] - sp[it] + MOD) * lvl[nod] * sp[it]) % MOD;
}
}
sp[nod] += w[nod];
mod(sp[nod]);
return ans;
}
inline int solve(int N, int *X, int *Y, VVI &cx, VVI &cy, VI &nrm_x, VI &nrm_y) {
map <PII, int> mp, vis;
VVI g(N + 1);
VI w(N + 1);
int i, cur = 0;
for(int x = 1; x <= N; x++) {
sort(cx[x].begin(), cx[x].end());
int sz = cx[x].size();
i = 0;
while(i < sz) {
int j = i;
cur++;
while(j < sz && cx[x][i] + j - i == cx[x][j]) {
auto it = mp[{nrm_x[x] - 1, cx[x][j]}];
if(it != 0) {
if(vis[{it, cur}] == 0) {
g[cur].push_back(it);
g[it].push_back(cur);
vis[{it, cur}] = vis[{cur, it}] = 1;
}
}
it = mp[{nrm_x[x] + 1, cx[x][j]}];
if(it != 0) {
if(vis[{it, cur}] == 0) {
g[cur].push_back(it);
g[it].push_back(cur);
vis[{it, cur}] = vis[{cur, it}] = 1;
}
}
w[cur]++;
mp[{nrm_x[x], cx[x][j]}] = cur;
j++;
}
i = j;
}
}
VI lvl(N + 1), sp(N + 1);
int aux = dfs(1, 0, g, w, lvl, sp);
int ans = 0;
for(i = 1; i <= cur; i++) {
ans = (ans + 1LL * w[i] * lvl[i] * (N - w[i])) % MOD;
}
mod(aux);
ans += MOD - aux;
mod(ans);
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
VVI cx(N + 1), cy(N + 1);
VI nrm_x(N + 1), nrm_y(N + 1);
map <int, int> mpx, mpy;
int curx = 0, cury = 0;
for(int i = 0; i < N; i++) {
if(mpx[X[i]] == 0) {
curx++;
mpx[X[i]] = curx;
nrm_x[curx] = X[i];
}
if(mpy[Y[i]] == 0) {
cury++;
mpy[Y[i]] = cury;
nrm_y[cury] = Y[i];
}
cx[mpx[X[i]]].push_back(Y[i]);
cy[mpy[Y[i]]].push_back(X[i]);
}
int ans = solve(N, X, Y, cx, cy, nrm_x, nrm_y);
ans += solve(N, Y, X, cy, cx, nrm_y, nrm_x);
mod(ans);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |