Submission #1020823


Source Code Expand

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

using namespace std;

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)]);
  }
};

typedef long long int64;
const int INF = 1 << 30;

int64 N, R, s, t;
int64 a[100000], b[100000];
UnionFind tree(100000);
int64 ret[100000];

void ask(int v)
{
  map< int, vector< pair< int64, int > > > backet;
  for(int i = 0; i < N; i++) {
    backet[a[i]].push_back(make_pair(b[i], i));
  }
  for(auto &obj : backet) {
    sort(begin(obj.second), end(obj.second));
  }
  for(int i = 0; i < N; i++) {
    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++) {
    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);
  }
}

int 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);
  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
Task E - Manhattan Compass
User ei13333
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1911 Byte
Status
Exec Time 264 ms
Memory 29148 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 640 KB
subtask0_1.txt 3 ms 640 KB
subtask0_2.txt 3 ms 640 KB
subtask1_0.txt 220 ms 28524 KB
subtask1_1.txt 215 ms 28524 KB
subtask1_10.txt 221 ms 11264 KB
subtask1_11.txt 118 ms 5376 KB
subtask1_12.txt 215 ms 28892 KB
subtask1_13.txt 216 ms 29020 KB
subtask1_14.txt 264 ms 19584 KB
subtask1_15.txt 118 ms 5376 KB
subtask1_16.txt 231 ms 29148 KB
subtask1_17.txt 228 ms 28636 KB
subtask1_18.txt 133 ms 5632 KB
subtask1_19.txt 118 ms 5376 KB
subtask1_2.txt 261 ms 20608 KB
subtask1_20.txt 235 ms 29020 KB
subtask1_21.txt 233 ms 29020 KB
subtask1_22.txt 126 ms 5648 KB
subtask1_23.txt 121 ms 5376 KB
subtask1_24.txt 230 ms 29148 KB
subtask1_3.txt 121 ms 5376 KB
subtask1_4.txt 239 ms 28780 KB
subtask1_5.txt 233 ms 28780 KB
subtask1_6.txt 133 ms 5720 KB
subtask1_7.txt 120 ms 5376 KB
subtask1_8.txt 213 ms 28396 KB
subtask1_9.txt 230 ms 28524 KB