oj.uz

Submission #501033

# Submission time Handle Problem Language Result Execution time Memory
501033 2022-01-02T09:13:10 Z 600Mihnea Flood (IOI07_flood) C++17
100 / 100
 186 ms 14192 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 7;
int n;
int m;
int x[N];
int y[N];
int ord[N];
bool vis[N];
bool onCyc[N];
int g[N][4];
int edgeID[N][4];


int getDirection(int i, int j) {
  assert(x[i] == x[j] || y[i] == y[j]);
  if (x[i] == x[j]) {
    if (y[i] < y[j]) {
      return 0;
    } else {
      return 2;
    }
  } else {
    if (x[i] < x[j]) {
      return 3;
    } else {
      return 1;
    }
  }
}

bool cmp(int i, int j) {
  if (x[i] != x[j]) {
    return x[i] < x[j];
  } else {
    return y[i] < y[j];
  }
}


void draw() {
  if (1) {
    return;
  }
  vector<vector<int>> tab(11, vector<int> (11, 0));
  for (int i = 1; i <= n; i++) {
    assert(0 <= x[i] && x[i] < (int) tab.size());
    assert(0 <= y[i] && y[i] < (int) tab[x[i]].size());
    swap(x[i], y[i]);
    tab[x[i]][y[i]] = -i;
    if (vis[i]) {
      tab[x[i]][y[i]] = 2;
    }
    if (onCyc[i]) {
      tab[x[i]][y[i]] = 3;
    }
    swap(x[i], y[i]);
  }
  for (int i = (int) tab.size() - 1; i >= 0; i--) {
    for (int j = 0; j < (int) tab[i].size(); j++) {
      if (tab[i][j] == 1) {
        cout << "*";
      }
      if (tab[i][j] == 2) {
        cout << "#";
      }
      if (tab[i][j] == 3) {
        cout << "C";
      }
      if (tab[i][j] == 0) {
        cout << " ";
      }
      if (tab[i][j] < 0) {
        cout << (-tab[i][j]) % 10;
      }
    }
    cout << "\n";
  }
  cout << "------------------------------\n";
}

int steps = 0;
vector<int> dirs;
bool act[N];
bool bad[N];
bool ok[2 * N];

int dfs(int a, int dir) {
  if (act[a]) {
    return a;
  }

 // cout << " = " << a << "\n";
  act[a] = 1;
  vis[a] = 1;
  ///draw();
  if (0) {
    cout << " ---> ";
    for (auto &d : dirs) {
      cout << d << " ";
    }
    cout << "\n";
  }
  steps++;
  for (int add = -1; add <= +1; add++) {
    int newDir = (dir + add + 4) % 4;
    if (g[a][newDir]) {
      int b = g[a][newDir];
      g[a][newDir] = 0;
      g[b][(newDir + 2) % 4] = 0;
      int cyc = dfs(b, newDir);
      if (cyc) {
        ok[edgeID[a][newDir]] = 1;
        if (cyc != a) {
          act[a] = 0;
          return cyc;
        }
      }
    }
  }

  act[a] = 0;
  return 0;
}

int ff[2 * N], ss[2 * N];


int main() {
  //freopen ("input", "r", stdin);
  bool home = 0;

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
    if (home)
    cout << x[i] << " " << y[i] << " " << i << "\n";
    ord[i] = i;
  }

  draw();

  cin >> m;

  for (int it = 1; it <= m; it++) {
    int i, j, dij, dji;
    cin >> i >> j;
    ff[it] = i;
    ss[it] = j;
    if (home)
    cout << "Segment " << x[i] << " " << y[i] << " " << x[j] << " " << y[j] << "\n";
    dij = getDirection(i, j);
    dji = getDirection(j, i);
    assert(g[i][dij] == 0);
    assert(g[j][dji] == 0);
    g[i][dij] = j;
    g[j][dji] = i;
    edgeID[i][dij] = it;
    edgeID[j][dji] = it;
  }
  int cnt = 0;

  sort(ord + 1, ord + n + 1, cmp);

  for (int j = 1; j <= n; j++) {
    int i = ord[j];
   // if (!vis[i]) {
      dfs(i, 3);
      draw();
      cnt++;
     // exit(0);
     // cout << "\n";
    //}
  }

  int cntBad = 0;
  for (int i = 1; i <= m; i++) {
    cntBad += !ok[i];
  }
  cout << cntBad << "\n";

  for (int i = 1; i <= m; i++) {
    if (!ok[i]) {
      if (!home)
      cout << i << "\n";
      else {
        cout << ff[i] << " " << ss[i] << "\n";
      }
    }
  }

  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1752 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 6660 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 5216 KB Output is correct
2 Correct 163 ms 6888 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 6396 KB Output is correct
2 Correct 171 ms 9492 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 6596 KB Output is correct
2 Correct 150 ms 14192 KB Output is correct