Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #1019760

Source Code Expand

Copy
```#include <bits/stdc++.h>

using namespace std;
#define int long long

struct UnionFind
{
vector< int > data;

UnionFind(int sz)
{
data.assign(sz, -1);
}

void unite(int x, int y)
{
x = find(x), y = find(y);
if(x != y) {
if(data[x] > data[y]) swap(x, y);
data[x] += data[y];
data[y] = x;
}
}

int find(int k)
{
if(data[k] < 0) return (k);
return (data[k] = find(data[k]));
}

int size(int k)
{
return (-data[find(k)]);
}
};

int N, R, s, t;
int a[100000], b[100000];
UnionFind tree(100000);
int ret[100000];
const int INF = 1LL << 59;

void ask(int v)
{
map< int, vector< pair< int, int > > > backet;
for(int i = 0; i < N; i++) {
backet[a[i]].push_back(make_pair(b[i], i));
}
for(auto &obj : backet) {
vector< pair< int, int > > &cc = obj.second;
sort(begin(cc), end(cc));
for(int j = 1; j < cc.size(); j++) {
//tree.unite(cc[j - 1].second, cc[j].second);
}
}
for(int i = 0; i < N; i++) {
if(!backet.count(a[i] - R)) continue;
auto &cc = backet[a[i] - R];

auto p = lower_bound(begin(cc), end(cc), make_pair(b[i] - R - v, +INF));
auto q = lower_bound(begin(cc), end(cc), make_pair(b[i] + R + v, -INF));
ret[i] += q - p;
if(p != q) tree.unite(i, p->second);
}
for(int i = 0; i < N; i++) {
if(!backet.count(a[i] + R)) continue;
auto &cc = backet[a[i] + R];
auto p = lower_bound(begin(cc), end(cc), make_pair(b[i] - R - v, +INF));
auto q = lower_bound(begin(cc), end(cc), make_pair(b[i] + R + v, -INF));
ret[i] += q - p;
if(p != q) tree.unite(i, p->second);
}
}

signed main()
{
cin >> N >> s >> t;
for(int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
a[i] = x + y;
b[i] = x - y;
}
--s, --t;
R = max(abs(a[s] - a[t]), abs(b[s] - b[t]));
ask(false);
for(int i = 0; i < N; i++) swap(a[i], b[i]);
ask(true);

tree.unite(s, t);
long long res = 0;
for(int i = 0; i < N; i++) {
if(tree.find(i) == tree.find(s)) res += ret[i];
}
cout << res / 2 << endl;
}```

#### Submission Info

Submission Time 2016-12-10 22:03:51+0900 E - Manhattan Compass ei13333 C++14 (GCC 5.4.1) 900 2150 Byte AC 295 ms 14428 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All 900 / 900 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 3 ms 1024 KB
subtask0_1.txt 3 ms 1024 KB
subtask0_2.txt 3 ms 1024 KB
subtask1_0.txt 177 ms 14060 KB
subtask1_1.txt 170 ms 14060 KB
subtask1_10.txt 260 ms 9984 KB
subtask1_11.txt 140 ms 5760 KB
subtask1_12.txt 162 ms 14172 KB
subtask1_13.txt 174 ms 14172 KB
subtask1_14.txt 295 ms 12800 KB
subtask1_15.txt 140 ms 5760 KB
subtask1_16.txt 190 ms 14428 KB
subtask1_17.txt 186 ms 14172 KB
subtask1_18.txt 154 ms 6016 KB
subtask1_19.txt 140 ms 5760 KB
subtask1_2.txt 275 ms 13056 KB
subtask1_20.txt 196 ms 14300 KB
subtask1_21.txt 203 ms 14300 KB
subtask1_22.txt 147 ms 6044 KB
subtask1_23.txt 145 ms 5760 KB
subtask1_24.txt 189 ms 14300 KB
subtask1_3.txt 146 ms 5760 KB
subtask1_4.txt 213 ms 14188 KB
subtask1_5.txt 203 ms 14188 KB
subtask1_6.txt 160 ms 6272 KB
subtask1_7.txt 143 ms 5760 KB
subtask1_8.txt 164 ms 14060 KB
subtask1_9.txt 175 ms 14060 KB