oj.uz

Submission #54718

# Submission time Handle Problem Language Result Execution time Memory
54718 2018-07-04T18:33:16 Z 0^0(#1466) Flood (IOI07_flood) C++11
33 / 100
 106 ms 14180 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int,int> adj[100005][4];
pair<int, int> p[100005];
void push(int u, int v, int idx) {
	if (p[u].first == p[v].first) {
		if (p[u].second > p[v].second)
			adj[u][1] = { v,idx };
		else adj[u][3] = { v,idx };
	}
	else {
		if (p[u].first > p[v].first)
			adj[u][0] = { v,idx };
		else adj[u][2] = { v,idx };
	}
}
int dist[200005];
bool chk[200005];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &p[i].first, &p[i].second);
	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);
	}
	int idx = min_element(p + 1, p + 1 + n) - p;
	queue<pair<int, int> > q;
	for(int i=0;i<4;i++)
		if (adj[idx][i].first) {
			q.push({ idx,i });
			dist[adj[idx][i].second] = 0;
			break;
		}
	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 });
			}
		}
	}
	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:72: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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
flood.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[i].first, &p[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
flood.cpp:27: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 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
3.0 / 3.0

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

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 680 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2528 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 5596 KB Output isn't correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 8272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 11372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 14180 KB Output isn't correct
2 Halted 0 ms 0 KB -