| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 83070 | edenooo | 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<iostream>
#include<stdio.h>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;
#define INF 987654321
#define ll long long
#define MOD 1'000'000'000
int A[100101], B[100101];
vector<pair<int, int> > x; //x y
vector<pair<pair<int, int>, int> > s[100101]; //start end n
vector<int> cnt(100101), g[100101], sub(100101);
ll sum, res;
int h, NN;
int DFS(int n, int prev)
{
sub[n] = cnt[n];
sum += 1LL * h * cnt[n];
h++;
for (int i = 0; i < g[n].size(); i++)
{
int next = g[n][i];
if (next == prev) continue;
sub[n] += DFS(next, n);
}
h--;
return sub[n];
}
void DFS2(int n, int prev, ll sum2) //sum2를 전역에 박았다가 틀림, 바꾸다가 ll을 int로 써서 틀림
{
if (n != 0)
{
sum2 -= sub[n];
sum2 += NN - sub[n]; //NN을 sum으로 했다가 틀림
}
res += sum2 * cnt[n]; //cnt[n]을 안 곱해 줘서 틀림
for (int i = 0; i < g[n].size(); i++)
{
int next = g[n][i];
if (next == prev) continue;
DFS2(next, n, sum2);
}
}
int f(int N, int *X, int *Y) //사실 (y,x)로 X와 Y가 바뀌어 있다.
{
NN = N;
x.clear();
for (int i = 0; i < 100101; i++) s[i].clear();
cnt = vector<int>(100101, 0);
for (int i = 0; i < 100101; i++) g[i].clear();
sub = vector<int>(100101, 0);
sum = 0, res = 0, h = 0;
for (int i = 0; i < N; i++)
x.push_back({ X[i], Y[i] });
sort(x.begin(), x.end());
int ord = 0, xx = 0, ss = x[0].second; //정점 생성
cnt[ord]++;
for (int i = 1; i < N; i++)
{
if (!(x[i].first == x[i - 1].first && x[i].second - 1 == x[i - 1].second)) //새로 만들어진 정점마다 start, end를 저장해 두면 정점끼리 연결되었는지를 쉽게 판단할 수 있다.
{
s[xx].push_back({ {ss, x[i - 1].second}, ord });
ord++;
ss = x[i].second;
}
if (x[i].first != x[i - 1].first)
xx++;
cnt[ord]++;
}
s[xx].push_back({ {ss, x[N - 1].second}, ord }); //항상 마지막 그룹은 따로 처리해줘야 한다.
for (int i = 1; i <= xx; i++) //그래프 생성
{
int a = 0, b = 0;
while (a < s[i - 1].size() && b < s[i].size())
{
int as = s[i - 1][a].first.first, ae = s[i - 1][a].first.second, an = s[i - 1][a].second;
int bs = s[i][b].first.first, be = s[i][b].first.second, bn = s[i][b].second;
if (as <= be && bs <= ae)
{
g[an].push_back(bn);
g[bn].push_back(an);
if (ae <= be) a++;
else b++;
}
else if (as > be) b++;
else a++;
}
}
DFS(0, -1);
DFS2(0, -1, sum);
return (res / 2) % MOD; //여기를 MOD 안 해줘서 틀림
}
int DistanceSum(int N, int *X, int *Y)
{
ll answer = 0;
answer += f(N, X, Y);
answer += f(N, Y, X);
return answer % MOD;
}
int main()
{
int N = 11;
int XX[11] = { 2,2,3,3,4,4,4,4,5,5,5 };
int YY[11] = { 5,6,3,6,3,4,5,6,3,4,6 };
int *X = (int*)malloc(N * sizeof(int)), *Y = (int*)malloc(N * sizeof(int));
for (int i = 0; i < N; i++)
X[i] = XX[i] + 2147483642;
for (int i = 0; i < N; i++)
Y[i] = YY[i] + 2147483641;
printf("%d", DistanceSum(N, X, Y));
return 0;
}