oj.uz

Submission #54725

# Submission time Handle Problem Language Result Execution time Memory
54725 2018-07-04T19:01:12 Z 0^0(#1466) Flood (IOI07_flood) C++11
100 / 100
 146 ms 13632 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> adj[100005][4];
pair<pair<int, int>,int> p[100005];
void push(int u, int v, int idx) {
	if (p[u].first.first == p[v].first.first) {
		if (p[u].first.second < p[v].first.second)
			adj[u][1] = { v,idx };
		else adj[u][3] = { v,idx };
	}
	else {
		if (p[u].first.first < p[v].first.first)
			adj[u][0] = { v,idx };
		else adj[u][2] = { v,idx };
	}
}
int dist[400005];
bool chk[400005];
void bfs(int idx, int dir) {
	queue<pair<int, int> > q;
	dist[adj[idx][dir].second] = 0;
	q.push({ idx,dir });
	while (!q.empty()) {
		int u = q.front().first;
		int dir = q.front().second;
		int v = adj[u][dir].first;
		int now = dist[adj[u][dir].second];
		q.pop();
		vector<pair<int, int> > vec;
		while (!chk[adj[u][dir].second]) {
			chk[adj[u][dir].second] = true;
			dist[adj[u][dir].second] = now;
			vec.push_back({ u,dir });
			for (int i = 0; i < 4; i++) {
				if (adj[v][(dir + 3 + i) % 4].first) {
					u = v;
					v = adj[v][(dir + 3 + i) % 4].first;
					dir = (dir + 3 + i) % 4;
					break;
				}
			}
		}
		for (auto &e : vec) {
			int idx = adj[e.first][e.second].second;
			int ridx = idx ^ 1;
			if (!chk[ridx]) {
				dist[ridx] = dist[idx] + 1;
				q.push({ adj[e.first][e.second].first,(e.second + 2) % 4 });
			}
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &p[i].first.first, &p[i].first.second);
		p[i].second = i;
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		push(a, b, i * 2);
		push(b, a, i * 2 + 1);
	}
	sort(p + 1, p + 1 + n);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 4; j++) {
			if (adj[p[i].second][j].first&&!chk[adj[p[i].second][j].second]) {
				bfs(p[i].second, j);
			}
		}
	}
	vector<int> ans;
	for (int i = 1; i <= m; i++) {
		if (dist[i * 2] == dist[i * 2 + 1])ans.push_back(i);
	}
	printf("%d\n", ans.size());
	for (auto x : ans)
		printf("%d\n", x);
	return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:79:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
flood.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
flood.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[i].first.first, &p[i].first.second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
flood.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2032 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5680 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5680 KB Output is correct
2 Correct 140 ms 6908 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 6908 KB Output is correct
2 Correct 142 ms 10212 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 10212 KB Output is correct
2 Correct 116 ms 13632 KB Output is correct