| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 54393 | 2018-07-03T09:59:46 Z | 강태규(#1471) | Flood (IOI07_flood) | C++11 | 525 ms | 33792 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
const int inf = 1e7;
const int MAXX = 1e6;
int n, w;
int x[100001];
int y[100001];
int as[200001];
int bs[200001];
int wall[100001][4];
struct point {
int x, y, up, dn;
bool operator<(const point &p) const {
if (x == p.x) return up < p.up;
return x < p.x;
}
} ps[400001];
vector<int> edge[400040];
int dist[400040];
bool visited[400040];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", x + i, y + i);
}
scanf("%d", &w);
for(int i = 1; i <= w; ++i) {
int a, b;
scanf("%d%d", &a, &b);
as[i] = a; bs[i] = b;
if (x[a] == x[b]) {
if (y[a] > y[b]) swap(a, b);
wall[a][1] = wall[b][3] = i;
edge[a << 2 | 1].push_back((b << 2 | 3) << 1 | 1);
edge[b << 2 | 3].push_back((a << 2 | 1) << 1 | 1);
}
else {
if (x[a] > x[b]) swap(a, b);
wall[a][0] = wall[b][2] = i;
edge[a << 2 | 0].push_back((b << 2 | 2) << 1 | 1);
edge[b << 2 | 2].push_back((a << 2 | 0) << 1 | 1);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 4; ++j) {
if (wall[i][j]) {
for (int c = (j + 1) & 3; ; c = (c + 1) & 3) {
if (wall[i][c]) {
int x = wall[i][c];
int a = as[x], b = bs[x];
int i2 = a ^ b ^ i, j2 = c ^ 2;
int x1 = i << 2 | j, x2 = i2 << 2 | j2;
edge[x1].push_back(x2 << 1);
edge[x2].push_back(x1 << 1);
break;
}
}
}
}
}
int m = 0;
for (int i = 1; i <= w; ++i) {
int a = as[i], b = bs[i];
if (x[a] == x[b]) continue;
if (x[a] > x[b]) swap(a, b);
int up = b << 2 | 2;
int dn = a << 2 | 0;
ps[m++] = { x[a], y[a], up, dn };
ps[m++] = { x[b], y[a], -1, 0 };
}
sort(ps, ps + m);
vector<int> ch;
map<int, pii> mp;
mp[-1] = mp[MAXX + 1] = pii(0, 0);
map<int, pii>::iterator it1, it2;
for (int i = 0, j = ps[0].x; i <= m; ++i) {
if (j < ps[i].x) {
for (int x : ch) {
it1 = mp.lower_bound(x);
it2 = it1--;
int a = it1->second.second;
int b = it2->second.first;
edge[a].push_back(b << 1);
edge[b].push_back(a << 1);
}
ch.clear();
j = ps[i].x;
}
if (i == m) break;
ch.push_back(ps[i].y);
ch.push_back(ps[i].y + 1);
if (ps[i].up < 0) mp.erase(ps[i].y);
else mp[ps[i].y] = pii(ps[i].up, ps[i].dn);
}
for (int i = 1; i <= (n << 2 | 3); ++i) dist[i] = inf;
deque<int> q;
q.push_back(0);
while (!q.empty()) {
int x = q.front();
q.pop_front();
if (visited[x]) continue;
visited[x] = 1;
for (int i : edge[x]) {
int j = i >> 1;
int d = dist[x] + (i & 1);
if (d < dist[j]) {
dist[j] = d;
if (i & 1) q.push_back(j);
else q.push_front(j);
}
}
}
vector<int> ans;
for(int i = 1; i <= w; ++i) {
int a = as[i], b = bs[i];
if (x[a] == x[b]) {
if (y[a] > y[b]) swap(a, b);
if (dist[a << 2 | 1] == dist[b << 2 | 3]) ans.push_back(i);
}
else {
if (x[a] > x[b]) swap(a, b);
if (dist[a << 2 | 0] == dist[b << 2 | 2]) ans.push_back(i);
}
}
printf("%d\n", (int)ans.size());
for (int i : ans) printf("%d\n", i);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 9720 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 9720 KB | Output is correct |
| 2 | Correct | 9 ms | 9992 KB | Output is correct |
| 3 | Correct | 9 ms | 9992 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 9992 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 9992 KB | Output is correct |
| 2 | Correct | 10 ms | 9992 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 9992 KB | Output is correct |
| 2 | Correct | 9 ms | 10016 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 10052 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 10092 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 10092 KB | Output is correct |
| 2 | Correct | 10 ms | 10092 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 10092 KB | Output is correct |
| 2 | Correct | 10 ms | 10172 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 44 ms | 13884 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 143 ms | 24320 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 220 ms | 26660 KB | Output is correct |
| 2 | Correct | 507 ms | 32732 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 418 ms | 32732 KB | Output is correct |
| 2 | Runtime error | 525 ms | 33792 KB | Memory limit exceeded |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 457 ms | 33792 KB | Memory limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |