oj.uz

Submission #283075

# Submission time Handle Problem Language Result Execution time Memory
283075 2020-08-25T09:36:48 Z kdh9949 Iqea (innopolis2018_final_C) C++17
0 / 100
 2000 ms 50856 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  
  vpii v;
  map<pii, int> ord;
  vector<vint> e(n + 1);
  const static int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
  for(int i = 1; i <= n; i++) {
    pii p;
    cin >> p.x >> p.y;
    int cur = int(ord.size()) + 1;
    ord[p] = cur;
    for(int j = 0; j < 4; j++) {
      pii t = {p.x + dx[j], p.y + dy[j]};
      if(ord.count(t)) {
        e[i].push_back(ord[t]);
        e[ord[t]].push_back(i);
      }
    }
    v.push_back(p);
  }

  vint gn(n + 1), sn(n + 1), id(n);
  iota(all(id), 0);
  sort(all(id), [&](int x, int y){ return v[x] < v[y]; });
  for(int i = 0, j, k = 1; i < n; i = j, k++) {
    for(j = i; j < n; j++) {
      if(v[id[i]].x != v[id[j]].x || v[id[j]].y - v[id[i]].y != j - i) break;
      sn[id[j] + 1] = k;
    } 
  }
  sort(all(id), [&](int x, int y){
    return pii(v[x].y, v[x].x) < pii(v[y].y, v[y].x);
  });
  for(int i = 0, j, k = 1; i < n; i = j, k++) {
    for(j = i; j < n; j++) {
      if(v[id[i]].y != v[id[j]].y || v[id[j]].x - v[id[i]].x != j - i) break;
      gn[id[j] + 1] = k;
    }
  }

  const static int L = 17;
  vector<vint> ge(n + 1), se(n + 1), gsp(L, vint(n + 1)), ssp(L, vint(n + 1));
  vint gdep(n + 1), sdep(n + 1);

  auto build_edge = [&](const vint &tn, vector<vint> &te) {
    for(int i = 1; i <= n; i++) for(int j : e[i]) {
      if(tn[i] != tn[j]) te[tn[i]].push_back(tn[j]);
    }
    for(int i = 1; i <= n; i++) te[i].erase(unique(all(te[i])), te[i].end());
  };
  build_edge(gn, ge); build_edge(sn, se);

  function<void(const vector<vint>&, vint&, vector<vint>&, int, int, int)> init_spt = [&](
    const vector<vint> &te, vint &dep, vector<vint> &sp,
    int x, int y, int z) {
    dep[x] = z;
    sp[0][x] = y;
    for(int i = 1; i < L; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]];
    for(int i : te[x]) if(i != y) init_spt(te, dep, sp, i, x, z + 1);
  };
  init_spt(ge, gdep, gsp, 1, 0, 1);
  init_spt(se, sdep, ssp, 1, 0, 1);

  auto dist = [&](const vector<vint> &sp, const vint &dep, int x, int y) {
    int r = dep[x] + dep[y];
    if(dep[x] > dep[y]) swap(x, y);
    for(int i = L - 1; i >= 0; i--) {
      if(((dep[y] - dep[x]) >> i) & 1) y = sp[i][y];
    }
    if(x == y) return r - 2 * dep[x];
    for(int i = L - 1; i >= 0; i--) {
      if(sp[i][y] != sp[i][x]) {
        y = sp[i][y];
        x = sp[i][x];
      }
    }
    return r - 2 * (dep[x] - 1);
  };

  vint d(n + 1, n);
  auto upd = [&](vint &v) {
    queue<int> q;
    for(int x : v) { d[x] = 0; q.push(x); }
    while(!q.empty()) {
      int x = q.front();
      q.pop();
      for(int i : e[x]) {
        if(d[i] > d[x] + 1) {
          d[i] = d[x] + 1;
          q.push(i);
        }
      }
    }
    v.clear();
  };

  int q;
  cin >> q;
  vint qv;
  const static int thr = 100;
  for(int i = 0; i < q; i++) {
    int t;
    pii p;
    cin >> t >> p.x >> p.y;
    if(t == 1) qv.push_back(ord[p]);
    else {
      if(qv.size() > thr) upd(qv);
      int x = ord[p];
      int ans = d[x];
      for(int y : qv) {
        ans = min(
          ans,
          dist(gsp, gdep, gn[x], gn[y]) + dist(ssp, sdep, sn[x], sn[y])
        );
      }
      cout << (ans == n ? -1 : ans) << '\n';
    }
  }

  return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1723 ms 432 KB Output is correct
4 Execution timed out 2025 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1723 ms 432 KB Output is correct
4 Execution timed out 2025 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 50856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 37740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1723 ms 432 KB Output is correct
4 Execution timed out 2025 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -