oj.uz

Submission #66569

# Submission time Handle Problem Language Result Execution time Memory
66569 2018-08-11T13:05:23 Z aome Flood (IOI07_flood) C++17
100 / 100
 166 ms 24880 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, m;
int p[N];
int e[N][4];
int fr[N * 2], to[N * 2];
pair<int, int> a[N];
int visit[N * 2][2];

void add(int u, int v, int id) {
	if (a[u].first == a[v].first) {
		if (a[u].second < a[v].second) e[u][1] = id; else e[u][3] = id;
	}
	else {
		if (a[u].first < a[v].first) e[u][2] = id; else e[u][0] = id;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
		cin >> a[i].first >> a[i].second;
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> fr[i] >> to[i];
		add(fr[i], to[i], i), add(to[i], fr[i], i);
	}
	sort(p + 1, p + 1 + n, [&] (int x, int y) {
		return a[x] < a[y];
	});
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		while (1) {
			bool found = 0;
			int u = p[i], d = 2;
			for (int j = 0; j < 4; ++j) {
				int id = e[u][j];
				found |= id && !visit[id][j < 2];
			}
			if (!found) break;
			++cnt;
			vector<int> buffer;
			while (1) {
				for (int j = 0; j < 4; ++j) {
					int k = (d + j + 3) % 4; 
					int id = e[u][k];
					if (id && !visit[id][k < 2]) {
						u = fr[id] + to[id] - u, d = k, visit[id][k < 2] = cnt, buffer.push_back(id); break;
					}
				}
				if (u == p[i]) break;
			}
			for (auto id : buffer) {
				if (!visit[id][0]) visit[id][0] = -1;
				if (!visit[id][1]) visit[id][1] = -1;
			}
		}
	}
	cnt = 0;
	for (int i = 1; i <= m; ++i) {
		if (visit[i][0] == visit[i][1]) cnt++;
	}
	cout << cnt << '\n';
	for (int i = 1; i <= m; ++i) {
		if (visit[i][0] == visit[i][1]) cout << i << '\n'; 
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2420 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7416 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9568 KB Output is correct
2 Correct 156 ms 13964 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 16208 KB Output is correct
2 Correct 147 ms 19664 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 22380 KB Output is correct
2 Correct 141 ms 24880 KB Output is correct