Submission #152404

#	Time	Username	Problem	Language	Result	Execution time	Memory
152404		flashmt	Flood (IOI07_flood)	C++17	100 / 100	104 ms	19576 KiB

flood

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;

struct Point
{
  int x, y, pos, wall[4], neighbor[4];

  bool operator <(const Point &u)
  {
    return make_pair(x, y) < make_pair(u.x, u.y);
  }
};

int n, turn, touch[N * 2], newpos[N], flag[N];
Point a[N];
pair<int, int> b[N * 2];

int getDirection(int u)
{
  for (int i = 1; i >= -2; i--)
  {
    int x = a[u].wall[(i + 4) % 4];
    if (x && !touch[x])
      return i;
  }
  return -1;
}

bool findBorder(int u, int pre, int start)
{
  if (u == start && flag[u] == turn)
    return 1;
  flag[u] = turn;

  for (int i = 1; i >= -2; i--)
  {
    int cur = (pre + i + 4) % 4;
    int x = a[u].wall[cur], y = a[u].neighbor[cur];
    a[u].wall[cur] = 0;
    if (x && touch[x] >= 0 && touch[x] < 2)
    {
      touch[x]++;
      if (findBorder(y, cur, start))
      {
        if (touch[x] == 1)
          touch[x] = -1;
        return 1;
      }
    }
  }

  return 0;
}

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

  int m, u, v;
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i].x >> a[i].y;
    a[i].pos = i;
  }
  cin >> m;
  for (int i = 1; i <= m; i++)
  {
    cin >> u >> v;
    b[i] = make_pair(u, v);
    int z;
    if (a[u].x == a[v].x) z = a[u].y < a[v].y ? 0 : 2;
    else z = a[u].x < a[v].x ? 1 : 3;
    a[u].wall[z] = i;
    a[v].wall[(z + 2) % 4] = i;
  }

  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++)
    newpos[a[i].pos] = i;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < 4; j++)
    {
      int z = a[i].wall[j], u = newpos[b[z].first], v = newpos[b[z].second];
      if (z)
        a[i].neighbor[j] = i == u ? v : u;
    }

  u = 1;
  while (1)
  {
    while (getDirection(u) < 0 && u <= n)
      ++u;
    if (u > n) break;
    ++turn;
    findBorder(u, getDirection(u), u);
  }

  vector<int> ans;
  for (int i = 1; i <= m; i++)
    if (touch[i] == 2)
      ans.push_back(i);
  cout << ans.size() << "\n";
  for (int x : ans)
    cout << x << "\n";
}

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