# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95315 | ics0503 | Flood (IOI07_flood) | C++17 | 177 ms | 33792 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { int x, y, w; }a[121212];
struct xxy { int x; char y; int w; };
bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y < b.y; return a.x < b.x; }
vector<xxy>edge[828282];
vector<int>Q[2];
int ck[121212][4], is_ans[221212], dist[828282], R[121212];
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;
sort(a + 1, a + P + 1, sort_y);
for (i = 1; i <= P; i++)R[a[i].w] = i;
scanf("%d", &L);
for (int i = 1; i <= L; i++) {
int s, e; scanf("%d%d", &s, &e);
s = R[s], e = R[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 * s + 6, 8 * e + 3, 0, 0);
addE(8 * s + 7, 8 * e + 2, 0, 0);
}
else {
if (a[s].y > a[e].y)swap(s, e);
ck[s][2] = i; ck[e][0] = i;
addE(8 * s + 4, 8 * e + 1, 0, 0);
addE(8 * s + 5, 8 * e + 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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |