| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 54397 |
2018-07-03T10:08:21 Z |
강태규(#1471) |
Flood (IOI07_flood) |
C++11 |
|
462 ms |
32392 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];
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);
int * ch = (int *)visited;
int tp = 0;
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 p = 0; p < tp; ++p) {
int x = ch[p];
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);
}
tp = 0;
j = ps[i].x;
}
if (i == m) break;
ch[tp++] = ps[i].y;
ch[tp++] = 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);
}
int * dist = (int *)ps;
dist[0] = 0;
visited[0] = 0;
for (int i = 1; i <= (n << 2 | 3); ++i) dist[i] = inf, visited[i] = 0;
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
flood.cpp: In function 'int main()':
flood.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
flood.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", x + i, y + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
flood.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &w);
~~~~~^~~~~~~~~~
flood.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9976 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
9976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
9976 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
10060 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
10060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
10060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
10080 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10080 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
10080 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10080 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
45 ms |
13600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
137 ms |
23032 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
142 ms |
25212 KB |
Output is correct |
| 2 |
Correct |
457 ms |
31084 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
370 ms |
31084 KB |
Output is correct |
| 2 |
Correct |
462 ms |
32392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
434 ms |
32392 KB |
Output is correct |
| 2 |
Correct |
306 ms |
32392 KB |
Output is correct |
