oj.uz

Submission #28204

# Submission time Handle Problem Language Result Execution time Memory
28204 2017-07-15T16:01:44 Z RayaBurong25_1 Ideal city (IOI12_city) C++14
100 / 100
 133 ms 13100 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#define MOD 1000000000
std::vector<std::pair<int, int> > XY;
int xtheny(std::pair<int, int> a, std::pair<int, int> b)
{
	return (a.first < b.first || (a.first == b.first && a.second < b.second));
}
int ythenx(std::pair<int, int> a, std::pair<int, int> b)
{
	return (a.second < b.second || (a.second == b.second && a.first < b.first));
}
int Ynode[100005];
int Xnode[100005];
typedef struct nodeY nodeY;
struct nodeY
{
	int xs, xe, y;
};
typedef struct nodeX nodeX;
struct nodeX
{
	int ys, ye, x;
};
std::vector<nodeY> InfY;
std::vector<nodeX> InfX;
std::vector<int> Sz;
std::vector<int> AdjList[100005];
long long Ans;
int DFS(int u, int pa, long long N)
{
	int i, v, s = AdjList[u].size();
	long long sub = 0;
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa)
			sub += DFS(v, u, N);
	}
	sub += Sz[u];
	Ans = (Ans + sub*(N - sub))%MOD;
	// printf("u%d pa%d N%lld sub%lld Ans%lld\n", u, pa, N, sub, Ans);
	return sub;
}
int DistanceSum(int N, int *X, int *Y)
{
	int i, j;
	for (i = 0; i < N; i++)
		XY.push_back({X[i], Y[i]});
	//group nodes by same X
	std::sort(XY.begin(), XY.end(), xtheny);
	int ys, ye, x = 0;
	for (j = 0; j < N; j++)
	{
		if (x == 0)
		{
			x = XY[j].first;
			ys = XY[j].second;
			ye = XY[j].second;
			i = 0;
			Xnode[i] = InfX.size();
		}
		else if (XY[j].second != ye + 1 || XY[j].first != x)
		{
			for (; i < j; i++)
				Xnode[i] = InfX.size();
			InfX.push_back({ys, ye, x});
			// printf("ys%d ye%d x%d\n", ys, ye, x);
			Sz.push_back(ye - ys + 1);
			x = XY[j].first;
			ys = XY[j].second;
			ye = XY[j].second;
		}
		else
			ye = XY[j].second;
	}
	for (; i < j; i++)
		Xnode[i] = InfX.size();
	InfX.push_back({ys, ye, x});
	// printf("ys%d ye%d x%d\n", ys, ye, x);
	Sz.push_back(ye - ys + 1);
	x = XY[j].first;
	ys = XY[j].second;
	ye = XY[j].second;
	for (i = 0; i < N; i++)
	{
		// printf("Xnode %d = %d\n", i, Xnode[i]);
		j = std::lower_bound(XY.begin(), XY.end(), std::make_pair(XY[i].first - 1, XY[i].second), xtheny) - XY.begin();
		// printf("j%d\n", j);
		if (j < N && XY[j].first == XY[i].first - 1 && XY[j].second == XY[i].second)
		{
			AdjList[Xnode[i]].push_back(Xnode[j]);
			AdjList[Xnode[j]].push_back(Xnode[i]);
			// printf("%d-%d\n", Xnode[i], Xnode[j]);
		}
		j = std::lower_bound(XY.begin(), XY.end(), std::make_pair(XY[i].first + 1, XY[i].second), xtheny) - XY.begin();
		// printf("j%d\n", j);
		if (j < N && XY[j].first == XY[i].first + 1 && XY[j].second == XY[i].second)
		{
			AdjList[Xnode[i]].push_back(Xnode[j]);
			AdjList[Xnode[j]].push_back(Xnode[i]);
			// printf("%d-%d\n", Xnode[i], Xnode[j]);
		}
	}
	std::vector<int>::iterator it;
	for (i = 0; i < InfX.size(); i++)
	{
		std::sort(AdjList[i].begin(), AdjList[i].end());
		it = std::unique(AdjList[i].begin(), AdjList[i].end());
		AdjList[i].erase(it, AdjList[i].end());
	}
	DFS(0, -1, N);

	for (i = 0; i < InfX.size(); i++)
		AdjList[i].clear();
	Sz.clear();

	//group nodes by same Y
	std::sort(XY.begin(), XY.end(), ythenx);
	int xs, xe, y = 0;
	for (j = 0; j < N; j++)
	{
		if (y == 0)
		{
			y = XY[j].second;
			xs = XY[j].first;
			xe = XY[j].first;
			i = 0;
			Ynode[i] = InfY.size();
		}
		else if (XY[j].first != xe + 1 || XY[j].second != y)
		{
			for (; i < j; i++)
				Ynode[i] = InfY.size();
			InfY.push_back({xs, xe, y});
			// printf("xs%d xe%d y%d\n", xs, xe, y);
			Sz.push_back({xe - xs + 1});
			y = XY[j].second;
			xs = XY[j].first;
			xe = XY[j].first;
		}
		else
			xe = XY[j].first;
	}
	for (; i < j; i++)
		Ynode[i] = InfY.size();
	InfY.push_back({xs, xe, y});
	// printf("xs%d xe%d y%d\n", xs, xe, y);
	Sz.push_back({xe - xs + 1});
	y = XY[j].second;
	xs = XY[j].first;
	xe = XY[j].first;
	for (i = 0; i < N; i++)
	{
		// printf("Ynode %d = %d\n", i, Ynode[i]);
		j = std::lower_bound(XY.begin(), XY.end(), std::make_pair(XY[i].first, XY[i].second - 1), ythenx) - XY.begin();
		// printf("j%d\n", j);
		if (j < N && XY[j].first == XY[i].first && XY[j].second == XY[i].second - 1)
		{
			AdjList[Ynode[i]].push_back(Ynode[j]);
			AdjList[Ynode[j]].push_back(Ynode[i]);
			// printf("%d-%d\n", Ynode[i], Ynode[j]);
		}
		j = std::lower_bound(XY.begin(), XY.end(), std::make_pair(XY[i].first, XY[i].second + 1), ythenx) - XY.begin();
		// printf("j%d\n", j);
		if (j < N && XY[j].first == XY[i].first && XY[j].second == XY[i].second + 1)
		{
			AdjList[Ynode[i]].push_back(Ynode[j]);
			AdjList[Ynode[j]].push_back(Ynode[i]);
			// printf("%d-%d\n", Ynode[i], Ynode[j]);
		}
	}
	for (i = 0; i < InfY.size(); i++)
	{
		std::sort(AdjList[i].begin(), AdjList[i].end());
		it = std::unique(AdjList[i].begin(), AdjList[i].end());
		AdjList[i].erase(it, AdjList[i].end());
	}
	DFS(0, -1, N);
	return (int) Ans;
}

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:107:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < InfX.size(); i++)
                ^
city.cpp:115:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < InfX.size(); i++)
                ^
city.cpp:174:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < InfY.size(); i++)
                ^
city.cpp:150:19: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Sz.push_back({xe - xs + 1});
                   ^
city.cpp:150:19: warning: 'xe' may be used uninitialized in this function [-Wmaybe-uninitialized]
city.cpp:82:18: warning: 'ye' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Sz.push_back(ye - ys + 1);
                  ^
city.cpp:82:18: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 0 ms 4444 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 0 ms 4576 KB Output is correct
4 Correct 3 ms 4576 KB Output is correct
5 Correct 0 ms 4576 KB Output is correct
6 Correct 3 ms 4576 KB Output is correct
7 Correct 0 ms 4576 KB Output is correct
8 Correct 3 ms 4576 KB Output is correct
9 Correct 3 ms 4576 KB Output is correct
10 Correct 0 ms 4576 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5452 KB Output is correct
2 Correct 16 ms 5872 KB Output is correct
3 Correct 49 ms 6472 KB Output is correct
4 Correct 49 ms 7336 KB Output is correct
5 Correct 109 ms 8880 KB Output is correct
6 Correct 109 ms 11080 KB Output is correct
7 Correct 106 ms 10180 KB Output is correct
8 Correct 109 ms 8892 KB Output is correct
9 Correct 99 ms 10076 KB Output is correct
10 Correct 113 ms 13100 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5648 KB Output is correct
2 Correct 19 ms 5688 KB Output is correct
3 Correct 63 ms 7616 KB Output is correct
4 Correct 59 ms 7360 KB Output is correct
5 Correct 133 ms 10732 KB Output is correct
6 Correct 129 ms 10016 KB Output is correct
7 Correct 126 ms 10860 KB Output is correct
8 Correct 116 ms 9764 KB Output is correct
9 Correct 113 ms 9724 KB Output is correct
10 Correct 113 ms 9896 KB Output is correct