답안 #95309 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95309	2019-01-30T03:10:06 Z	ics0503	Flood (IOI07_flood)	C++17	42 / 100	130 ms	33792 KB

flood

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { int x, y, w; }a[121212];
bool sort_x(xy a, xy b) { if (a.x != b.x)return a.x < b.x; return a.y < b.y; }
bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y < b.y; return a.x < b.x; }
vector<xy>edge[828282];
vector<int>Q[2];
int ck[121212][4], is_ans[121212], dist[828282];
void swap(int &a, int &b) { a ^= b ^= a ^= b; }
void addE(int s, int e, int w, int i) {
	edge[s].push_back({ e, w , i});
	edge[e].push_back({ s, w , i});
}
int main() {
	int P, L, i, j; scanf("%d", &P);
	for (i = 1; i <= P; i++)scanf("%d%d", &a[i].x, &a[i].y), a[i].w = i;
	scanf("%d", &L);
	for (int i = 1; i <= L; i++) {
		int s, e; scanf("%d%d", &s, &e);
		if (a[s].y == a[e].y) {
			if (a[s].x > a[e].x)swap(s, e);
			ck[s][3] = i; ck[e][1] = i;
			addE(8 * a[s].w + 6, 8 * a[e].w + 3, 0, 0);
			addE(8 * a[s].w + 7, 8 * a[e].w + 2, 0, 0);
		}
		else {
			if (a[s].y > a[e].y)swap(s, e);
			ck[s][2] = i; ck[e][0] = i;
			addE(8 * a[s].w + 4, 8 * a[e].w + 1, 0, 0);
			addE(8 * a[s].w + 5, 8 * a[e].w + 0, 0, 0);
		}
	}
	int n = (P + 1) * 8 - 1;
	for (int i = 1; i <= P; i++) for (int j = 0; j < 4; j++) {
		addE(i * 8 + 2 * j, i * 8 + 2 * j + 1, !!ck[i][j], ck[i][j]);
		addE(i * 8 + 2 * j + 1, i * 8 + (2 * j + 2) % 8, 0, 0);
	}
	for (int i = 8; i <= n; i++) {
		if (dist[i]) continue;
		int dst; dst = dist[i] = 1; Q[1].push_back(i);
		while (!(Q[0].empty() && Q[1].empty())) {
			if (Q[dst % 2].empty()) {
				dst++;
				continue;
			}
			int now = Q[dst % 2].back(); Q[dst % 2].pop_back();
			if (dist[now] % 2 != dst % 2)continue;
			for (auto E : edge[now]) {
				if (dist[E.x] == 0 || dist[E.x] > dst + E.y) {
					dist[E.x] = dst + E.y;
					Q[(dst + E.y) % 2].push_back(E.x);
				}
			}
		}
	}
	for (int i = 8; i <= n; i++) for (auto E : edge[i]) if (dist[i] == dist[E.x]) is_ans[E.w] = 1; 
	int ansCnt = 0;
	for (int i = 1; i <= L; i++) if (is_ans[i])ansCnt++;
	printf("%d\n", ansCnt);
	for (int i = 1; i <= L; i++) if (is_ans[i])printf("%d\n", i);
	return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:17:15: warning: unused variable 'j' [-Wunused-variable]
  int P, L, i, j; scanf("%d", &P);
               ^
flood.cpp:17:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int P, L, i, j; scanf("%d", &P);
                  ~~~~~^~~~~~~~~~
flood.cpp:18:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= P; i++)scanf("%d%d", &a[i].x, &a[i].y), a[i].w = i;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
flood.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &L);
  ~~~~~^~~~~~~~~~
flood.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	19832 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	19860 KB	Output is correct
2	Correct	19 ms	19768 KB	Output is correct
3	Correct	18 ms	19832 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	19832 KB	Output is correct

Subtask #4
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	19 ms	19804 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19808 KB	Output is correct
2	Incorrect	19 ms	19796 KB	Output isn't correct

Subtask #6
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19832 KB	Output is correct

Subtask #7
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19960 KB	Output is correct

Subtask #8
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	19960 KB	Output is correct
2	Correct	19 ms	20056 KB	Output is correct

Subtask #9
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	19960 KB	Output is correct
2	Correct	31 ms	19964 KB	Output is correct

Subtask #10
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	68 ms	30200 KB	Output isn't correct

Subtask #11
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	86 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #12
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	89 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	127 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	130 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-