제출 #121964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121964		turbat	Flood (IOI07_flood)	C++14	0 / 100	269 ms	5664 KiB

flood

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9