Submission #83071

#	Time	Username	Problem	Language	Result	Execution time	Memory
83071		edenooo	Ideal city (IOI12_city)	C++17	100 / 100	95 ms	19936 KiB

city

#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;
}

Compilation message (stderr)

city.cpp: In function 'int DFS(int, int)':
city.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[n].size(); i++)
                  ~~^~~~~~~~~~~~~
city.cpp: In function 'void DFS2(int, int, long long int)':
city.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[n].size(); i++)
                  ~~^~~~~~~~~~~~~
city.cpp: In function 'int f(int, int*, int*)':
city.cpp:98:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a < s[i - 1].size() && b < s[i].size())
          ~~^~~~~~~~~~~~~~~~~
city.cpp:98:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a < s[i - 1].size() && b < s[i].size())
                                 ~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45