| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291579 |
2020-09-05T13:46:55 Z |
Kastanda |
Flood (IOI07_flood) |
C++11 |
|
495 ms |
65540 KB |
// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 100005 * 2 * 2, MXK = 1e6 + 3;
int n, m, V[N], U[N], D[N], M[N];
pair < int , int > A[N];
vector < int > E[N], Events[MXK];
vector < pair < int , int > > Adj[N];
inline void AddEdge(int v, int u, int w)
{
Adj[v].push_back({u, w});
Adj[u].push_back({v, w});
}
int main()
{
/* Main philosophy :
Each edge has two sides, denoted by i*2-1 (left, down) and i*2 (right, up)
*/
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d%d", &A[i].x, &A[i].y);
scanf("%d", &m);
for (int i = 1; i <= m; i ++)
{
scanf("%d%d", &V[i], &U[i]);
E[V[i]].push_back(i);
E[U[i]].push_back(i);
}
for (int i = 1; i <= n; i ++)
{
int l, r, d, u;
l = r = d = u = 0;
for (int e : E[i])
{
int j = i ^ V[e] ^ U[e];
if (A[j].x < A[i].x)
l = e;
else if (A[j].x > A[i].x)
r = e;
else if (A[j].y < A[i].y)
d = e;
else
u = e;
}
// Now for the tedious casework :
// 1. l with d and u
if (l && d)
AddEdge(l * 2 - 1, d * 2 - 1, 0);
if (l && u)
AddEdge(l * 2, u * 2 - 1, 0);
// 2. r with d and u
if (r && d)
AddEdge(r * 2 - 1, d * 2, 0);
if (r && u)
AddEdge(r * 2, u * 2, 0);
// 3. l with r
if (l && r && !d)
AddEdge(l * 2 - 1, r * 2 - 1, 0);
if (l && r && !u)
AddEdge(l * 2, r * 2, 0);
// 4. d with u
if (d && u && !l)
AddEdge(d * 2 - 1, u * 2 - 1, 0);
if (d && u && !r)
AddEdge(d * 2, u * 2, 0);
}
for (int w = 0; w <= 1; w ++)
{
for (int i = 1; i <= m; i ++)
if (A[V[i]].x == A[U[i]].x)
Events[A[V[i]].x].push_back(i);
set < pair < pair < int , int > , int > > ST;
for (int i = 0; i < MXK; i ++)
for (int e : Events[i])
{
int ly = A[V[e]].y, ry = A[U[e]].y;
if (ly > ry) swap(ly, ry);
auto it = ST.lower_bound({{ly, -1}, -1});
if (it != ST.begin())
{
it --;
if (it->first.second > ly)
{
AddEdge(e * 2 - 1, it->second * 2, 0);
auto TMp = * it;
TMp.first.second = ly;
it = ST.erase(it);
ST.insert(TMp);
it --;
assert(* it == TMp);
}
it ++;
}
while (it != ST.end() && it->first.second <= ry)
AddEdge(e * 2 - 1, it->second * 2, 0), it = ST.erase(it);
if (it != ST.end() && it->first.first < ry)
{
AddEdge(e * 2 - 1, it->second * 2, 0);
auto TMp = * it;
TMp.first.first = ry;
it = ST.erase(it);
ST.insert(TMp);
it --;
assert(* it == TMp);
}
ST.insert({{ly, ry}, e});
}
for (int i = 0; i < MXK; i ++)
Events[i].clear();
for (int i = 1; i <= m; i ++)
swap(A[i].x, A[i].y);
}
for (int i = 1; i <= m; i ++)
AddEdge(i * 2, i * 2 - 1, 1);
deque < int > Dq;
memset(D, 63, sizeof(D));
for (int i = 1; i <= m * 2; i ++)
if ((int)Adj[i].size() == 1)
D[i] = 0, Dq.push_back(i);
while (Dq.size())
{
int v = Dq.front();
Dq.pop_front();
if (M[v])
continue;
M[v] = 1;
for (auto u : Adj[v])
if (D[u.x] > D[v] + u.y)
{
D[u.x] = D[v] + u.y;
if (!u.y) Dq.push_front(u.x);
else Dq.push_back(u.x);
}
}
vector < int > Rs;
for (int i = 1; i <= m; i ++)
if (D[i * 2] == D[i * 2 - 1])
Rs.push_back(i);
printf("%d\n", (int)Rs.size());
for (int i : Rs)
printf("%d\n", i);
return 0;
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
21 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
flood.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
23 | scanf("%d%d", &A[i].x, &A[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
24 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
flood.cpp:27:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
27 | scanf("%d%d", &V[i], &U[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
44152 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
44200 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
44152 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
44240 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
44152 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
44220 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
44280 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
44412 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
44268 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
48888 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
61944 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
194 ms |
62908 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
495 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
437 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
