Submission #1004001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004001		MilosMilutinovic	Flood (IOI07_flood)	C++14	30 / 100	353 ms	55488 KiB

flood

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    x[i] *= 2;
    y[i] *= 2;
  }
  int m;
  cin >> m;
  vector<int> a(m);
  vector<int> b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    --a[i]; --b[i];
  }
  vector<pair<int, int>> pts;
  for (int i = 0; i < n; i++) {
    for (int dx = -1; dx <= 1; dx++) {
      for (int dy = -1; dy <= 1; dy++) {
        if (abs(dx) + abs(dy) == 2) {
          pts.emplace_back(x[i] + dx, y[i] + dy);
        }
      }
    }
  }
  sort(pts.begin(), pts.end());
  pts.erase(unique(pts.begin(), pts.end()), pts.end());
  int k = (int) pts.size();
  map<int, vector<int>> xs;
  map<int, vector<int>> ys;
  for (int i = 0; i < k; i++) {
    xs[pts[i].first].push_back(i);
    ys[pts[i].second].push_back(i);
  }
  vector<vector<pair<int, int>>> g(k);
  for (auto& p : xs) {
    vector<int> id = p.second;
    sort(id.begin(), id.end(), [&](int i, int j) {
      return pts[i].second < pts[j].second;
    });
    for (int i = 0; i + 1 < (int) id.size(); i++) {
      g[id[i]].emplace_back(id[i + 1], 0);
      g[id[i + 1]].emplace_back(id[i], 0);
    }
  }
  for (auto& p : ys) {
    vector<int> id = p.second;
    sort(id.begin(), id.end(), [&](int i, int j) {
      return pts[i].first < pts[j].first;
    });
    for (int i = 0; i + 1 < (int) id.size(); i++) {
      g[id[i]].emplace_back(id[i + 1], 0);
      g[id[i + 1]].emplace_back(id[i], 0);
    }
  }
  for (int i = 0; i < k; i++) {
    sort(g[i].begin(), g[i].end());
    g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
  }
  auto Index = [&](int x, int y) {
    pair<int, int> p = {x, y};
    return (int) (lower_bound(pts.begin(), pts.end(), p) - pts.begin());
  };
  auto Update = [&](int i, int j) {
    {
      int idx = (int) (lower_bound(g[i].begin(), g[i].end(), make_pair(j, -1)) - g[i].begin());
      g[i][idx].second = 1;
    }
    {
      int idx = (int) (lower_bound(g[j].begin(), g[j].end(), make_pair(i, -1)) - g[j].begin());
      g[j][idx].second = 1;
    }
  };
  for (int i = 0; i < m; i++) {
    if (x[a[i]] > x[b[i]] || y[a[i]] > y[b[i]]) {
      swap(a[i], b[i]);
    }
    if (x[a[i]] == x[b[i]]) {
      Update(Index(x[a[i]] - 1, y[a[i]] + 1), Index(x[a[i]] + 1, y[a[i]] + 1));
      Update(Index(x[b[i]] - 1, y[b[i]] - 1), Index(x[b[i]] + 1, y[b[i]] - 1));
    } else {
      Update(Index(x[a[i]] + 1, y[a[i]] + 1), Index(x[a[i]] + 1, y[a[i]] - 1));
      Update(Index(x[b[i]] - 1, y[b[i]] + 1), Index(x[b[i]] - 1, y[b[i]] - 1));
    }
  }
  const int inf = (int) 1e9;
  vector<int> dist(k, inf);
  vector<int> order(k);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return pts[i] < pts[j];
  });
  int cur = 0;
  for (int v : order) {
    if (dist[v] != inf) {
      continue;
    }
    dist[v] = cur;
    deque<int> dq;
    dq.push_back(v);
    while (!dq.empty()) {
      int i = dq.front();
      dq.pop_front();
      cur = max(cur, dist[i] + 1);
      for (auto& e : g[i]) {
        int j = e.first;
        int w = e.second;
        if (dist[j] > dist[i] + w) {
          dist[j] = dist[i] + w;
          if (w == 0) {
            dq.push_front(j);
          } else {
            dq.push_back(j);
          }
        }
      }
    }
  }
  vector<int> res;
  for (int i = 0; i < m; i++) {
    if (x[a[i]] == x[b[i]]) {
      if (dist[Index(x[a[i]] - 1, y[a[i]] + 1)] == dist[Index(x[a[i]] + 1, y[a[i]] + 1)]) {
        res.push_back(i);
      }
    } else {
      if (dist[Index(x[a[i]] + 1, y[a[i]] - 1)] == dist[Index(x[a[i]] + 1, y[a[i]] + 1)]) {
        res.push_back(i);
      }
    }
  }
  cout << (int) res.size() << '\n';
  for (int i = 0; i < (int) res.size(); i++) {
    cout << res[i] + 1 << '\n';
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 10 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9