oj.uz

Submission #152404

# Submission time Handle Problem Language Result Execution time Memory
152404 2019-09-07T22:19:40 Z flashmt Flood (IOI07_flood) C++17
100 / 100
 104 ms 19576 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2488 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9872 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8312 KB Output is correct
2 Correct 104 ms 10976 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10392 KB Output is correct
2 Correct 103 ms 10972 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10872 KB Output is correct
2 Correct 94 ms 19576 KB Output is correct