Submission #1869441


Source Code Expand

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
int N, A, B, f[100001], C[100001];
long long D, x[100001], y[100001];
typedef std::vector < std::pair < int, int > > vpii;
std::map < long long, vpii > M1, M2;
int F(int x)
{
	return f[x] == x ? x : f[x] = F(f[x]);
}
void add(int u, int v)
{
	u = F(u), v = F(v);
	f[u] = v;
}
inline int abs(int x)
{
	return x < 0 ? -x : x;
}
inline bool cmp_pair(std::pair < int, int > a, std::pair < int, int > b)
{
	return x[a.first] < x[b.first];
}
vpii::iterator lower_bound(vpii &V, long long w)
{
	auto Ol = V.begin(), Or = V.end();
	while (Ol < Or)
	{
		auto Om = Ol + (Or - Ol >> 1);
		if (x[Om -> first] >= w)
			Or = Om;
		else
			Ol = Om + 1;
	}
	return Ol;
}
vpii::iterator upper_bound(vpii &V, long long w)
{
	auto Ol = V.begin(), Or = V.end();
	while (Ol < Or)
	{
		auto Om = Ol + (Or - Ol >> 1);
		if (x[Om -> first] > w)
			Or = Om;
		else
			Ol = Om + 1;
	}
	return Ol;
}
void GetRange(int &Count, std::vector < int > &O, vpii &V, long long L, long long R)
{
	vpii::iterator first = lower_bound(V, L), second = upper_bound(V, R);
	Count += second - first;
	if (first < second)
	{
		O.push_back(first -> first);
		first -> second++;
		(second - 1) -> second--;
	}
}
int main()
{
	scanf("%d%d%d", &N, &A, &B);
	for (int i = 1; i <= N; i++)
		f[i] = i;
	for (int i = 1; i <= N; i++)
	{
		scanf("%lld%lld", x + i, y + i);
		M1[x[i] + y[i]].push_back(std::make_pair(i, 0));
		M2[x[i] - y[i]].push_back(std::make_pair(i, 0));
	}
	D = abs(x[A] - x[B]) + abs(y[A] - y[B]);
	for (auto &i : M1)
		std::sort(i.second.begin(), i.second.end(), cmp_pair);
	for (auto &i : M2)
		std::sort(i.second.begin(), i.second.end(), cmp_pair);
	for (int i = 1; i <= N; i++)
	{
		vpii &UL = M1[x[i] + y[i] - D], &UR = M2[x[i] - y[i] - D], &DL = M2[x[i] - y[i] + D], &DR = M1[x[i] + y[i] + D];
		std::vector < int > tmp;
		GetRange(C[i], tmp, UL, x[i] - D, x[i] - 1);
		GetRange(C[i], tmp, UR, x[i] - D + 1, x[i]);
		GetRange(C[i], tmp, DL, x[i], x[i] + D - 1);
		GetRange(C[i], tmp, DR, x[i] + 1, x[i] + D);
		for (int j : tmp)
			add(i, j);
	}
	for (auto &e : M1)
	{
		vpii &V = e.second;
		for (size_t i = 1; i < V.size(); i++)
			V[i].second += V[i - 1].second;
		for (size_t i = 0; i + 1 < V.size(); i++)
			if (V[i].second)
				add(V[i].first, V[i + 1].first);
	}
	for (auto &e : M2)
	{
		vpii &V = e.second;
		for (size_t i = 1; i < V.size(); i++)
			V[i].second += V[i - 1].second;
		for (size_t i = 0; i + 1 < V.size(); i++)
			if (V[i].second)
				add(V[i].first, V[i + 1].first);
	}
	long long O = 0;
	for (int i = 1; i <= N; i++)
		if (F(i) == F(A))
			O += C[i];
	printf("%lld\n", O >> 1);
	return 0;
}

Submission Info

Submission Time
Task E - Manhattan Compass
User NiroBC
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2776 Byte
Status AC
Exec Time 305 ms
Memory 37632 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &A, &B);
                             ^
./Main.cpp:70:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", x + i, y + i);
                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 28
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_2.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask1_0.txt AC 219 ms 28920 KB
subtask1_1.txt AC 214 ms 28792 KB
subtask1_10.txt AC 232 ms 17664 KB
subtask1_11.txt AC 104 ms 5120 KB
subtask1_12.txt AC 193 ms 29304 KB
subtask1_13.txt AC 194 ms 29304 KB
subtask1_14.txt AC 305 ms 35200 KB
subtask1_15.txt AC 105 ms 5120 KB
subtask1_16.txt AC 247 ms 29560 KB
subtask1_17.txt AC 234 ms 28920 KB
subtask1_18.txt AC 144 ms 5376 KB
subtask1_19.txt AC 104 ms 5120 KB
subtask1_2.txt AC 278 ms 37632 KB
subtask1_20.txt AC 244 ms 29432 KB
subtask1_21.txt AC 240 ms 29432 KB
subtask1_22.txt AC 132 ms 5376 KB
subtask1_23.txt AC 116 ms 5120 KB
subtask1_24.txt AC 233 ms 29560 KB
subtask1_3.txt AC 113 ms 5120 KB
subtask1_4.txt AC 252 ms 29048 KB
subtask1_5.txt AC 241 ms 29176 KB
subtask1_6.txt AC 146 ms 5504 KB
subtask1_7.txt AC 117 ms 5120 KB
subtask1_8.txt AC 196 ms 28920 KB
subtask1_9.txt AC 242 ms 28920 KB