제출 #121958

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

flood

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define N 100005

int n, w, k, id[N], beg;

pair <int, int> wall[N][4], pos[N];
pair <pair <int, int>, int > p[N];
bool vis[2 * N], brok[2 * N], stacked[N];


int dfs(int dir, int u){
	// cout << u << endl;
	stacked[u] = 1;
	int t = dir + 3;
	t %= 4;
	// cout << u<< endl;s
	while (t != (dir + 2) % 4){
		if (!vis[wall[u][t].S]) {
			vis[wall[u][t].S] = 1;
			// cout << wall[u][t].S<< endl;
			if (stacked[wall[u][t].F]) {
				stacked[u] = 0; 
				brok[wall[u][t].S] = 1;
				return wall[u][t].F;
			}
			int cyc = dfs(t, wall[u][t].F);
			if (cyc != -1){
				brok[wall[u][t].S] = 1;
				if (cyc != u){
					stacked[u] = 0;
					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;
		pos[i] = p[i].F;
	}
	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;
		}
	}
	// for (int i = 1;i <= n;i++)
	// 	cout <<i << ' '<< wall[i][0].F << ' ' << wall[i][1].F << ' '<< wall[i][2].F << ' ' << wall[i][3].F<< endl;
	sort (p + 1, p + n + 1);
	for (int i = 1;i <= n;i++){
		// cout <<"######################\n";
		dfs(1, p[i].S);
	}
	// cout <<"#############################\n";
	for (int i = 1;i <= w;i++)
		if (!brok[i])
			k++;
	cout << k<< endl;
	for (int i = 1;i <= w;i++)
		if (!brok[i])
			cout << i << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9