이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define int int64_t
using namespace std;
struct tree
{
int n = 0;
int totsz = 0;
int res = 0;
vector<vector<int>> adjlist;
vector<int> vsz;
int dfs(int curr, int par)
{
int sz = vsz[curr];
for (auto next : adjlist[curr])
{
if (next == par) continue;
sz += dfs(next, curr);
}
res += sz*(totsz - sz);
return sz;
}
void addsz(int v)
{
vsz[v]++;
totsz++;
}
int addvertex()
{
n++;
adjlist.push_back(vector<int>());
vsz.push_back(0);
addsz(n - 1);
return n - 1;
}
void addedge(int a, int b)
{
adjlist[b].push_back(a);
adjlist[a].push_back(b);
}
};
int moves(int n, vector<pair<int,int>> pnts)
{
sort(pnts.begin(), pnts.end());
map<int,map<int,int>> mp;
tree t;
for (int i = 0; i < n; i++)
{
int y = pnts[i].first;
int x = pnts[i].second;
if (i > 0 && y == pnts[i - 1].first && x - 1 == pnts[i - 1].second)
{
mp[y][x] = mp[y][x - 1];
t.addsz(mp[y][x]);
if (mp[y - 1].find(x) == mp[y - 1].end()) continue;
if (mp[y - 1].find(x - 1) != mp[y - 1].end()) continue;
t.addedge(mp[y][x], mp[y-1][x]);
continue;
}
mp[y][x] = t.addvertex();
if (mp[y - 1].find(x) == mp[y - 1].end()) continue;
t.addedge(mp[y][x], mp[y - 1][x]);
}
t.dfs(0, -1);
return t.res;
}
signed DistanceSum(signed n, signed *X, signed *Y)
{
vector<pair<int,int>> pnts(n);
for (int i = 0; i < n; i++) pnts[i] = make_pair(X[i], Y[i]);
int res = moves(n, pnts);
for (int i = 0; i < n; i++) swap(pnts[i].first, pnts[i].second);
res += moves(n, pnts);
return res;
}
# | 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... |