oj.uz

Submission #121958

# Submission time Handle Problem Language Result Execution time Memory
121958 2019-06-27T09:40:27 Z turbat Flood (IOI07_flood) C++14
100 / 100
 400 ms 14896 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 7416 KB Output is correct
2 Correct 300 ms 9144 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 8720 KB Output is correct
2 Correct 289 ms 9248 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 9032 KB Output is correct
2 Correct 303 ms 14896 KB Output is correct