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
2017-12-13 21:50:55+0900
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
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