oj.uz

답안 #501014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501014 2022-01-02T07:50:47 Z 600Mihnea Flood (IOI07_flood) C++17
10 / 100
 181 ms 8120 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];

bool dfs(int a, int dir) {
  if (vis[a]) {
    return act[a];
  }
  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;
        act[a] = 0;

        return cyc;
      }
    }
  }

  act[a] = 0;
  return 0;
}

int main() {
 // freopen ("input", "r", stdin);

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

  draw();

  cin >> m;

  for (int it = 1; it <= m; it++) {
    int i, j, dij, dji;
    cin >> i >> j;
    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++;
    }
  }

  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]) {
      cout << i << "\n";
    }
  }

  return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 332 KB Output isn't correct

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #7
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 1976 KB Output isn't correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 110 ms 7972 KB Output isn't correct

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 141 ms 6728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 7732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 181 ms 8120 KB Output isn't correct
2 Halted 0 ms 0 KB -