oj.uz

Submission #121964

# Submission time Handle Problem Language Result Execution time Memory
121964 2019-06-27T09:53:04 Z turbat Flood (IOI07_flood) C++14
0 / 100
 269 ms 5664 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define N 100005

int n, w, k, cnt;
pair <int, int> wall[N][4];
pair <pair <int, int>, int > p[N];
bool vis[2 * N], brok[2 * N], stacked[N];

int dfs(int dir, int u){
  if (stacked[u]) return u;
  stacked[u] = 1;
  int t = dir + 3;
  t %= 4;
  while (t != (dir + 2) % 4){
    if (!vis[wall[u][t].S]) {
      vis[wall[u][t].S] = 1;
      int cyc = dfs(t, wall[u][t].F);
      if (cyc != -1){
        brok[wall[u][t].S] = 1;
        cnt--;
        stacked[u] = 0;
        if (cyc != u) return cyc;
      }
    }
    t++;
    t %= 4;
  }
  stacked[u] = 0;
  return -1;
}

int main (){
  vis[0] = 1;
  cin >> n;
  for (int i = 1;i <= n;i++) {
    p[i].S = i;
    cin >> p[i].F.F >> p[i].F.S;
  }
  cin >> w;
  for (int i = 1;i <= w;i++){
    int a, b;
    cin >> a >> b;
    if (p[a] > p[b]) swap(a, b);
    if (p[a].F.F == p[b].F.F){
      wall[a][2].F = b, wall[b][0].F = a;
      wall[a][2].S = wall[b][0].S = i;
    }
    else {
      wall[a][1].F = b, wall[b][3].F = a;
      wall[a][1].S = wall[b][3].S = i;
    }
  }
  sort (p + 1, p + n + 1);
  for (int i = 1;i <= n;i++) dfs(1, p[i].S);
  cout << w - k<< endl;
  for (int i = 1;i <= w;i++)
    if (!brok[i])
      cout << i << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 408 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1524 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 5664 KB Output isn't correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 269 ms 5388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 264 ms 5424 KB Output isn't correct
2 Halted 0 ms 0 KB -