| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291790 |
2020-09-05T19:09:31 Z |
Kastanda |
Flood (IOI07_flood) |
C++11 |
|
334 ms |
32624 KB |
// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 100005, MXK = 1e6 + 3;
int n, m, V[N * 2], U[N * 2], D[N * 4];
bitset < N * 4 > M;
pair < int , int > A[N];
vector < int > E[N];
vector < int > Ad[N * 4];
inline void AddEdge(int v, int u)
{
Ad[v].push_back(u);
Ad[u].push_back(v);
}
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);
if (l && u)
AddEdge(l * 2, u * 2 - 1);
// 2. r with d and u
if (r && d)
AddEdge(r * 2 - 1, d * 2);
if (r && u)
AddEdge(r * 2, u * 2);
// 3. l with r
if (l && r && !d)
AddEdge(l * 2 - 1, r * 2 - 1);
if (l && r && !u)
AddEdge(l * 2, r * 2);
// 4. d with u
if (d && u && !l)
AddEdge(d * 2 - 1, u * 2 - 1);
if (d && u && !r)
AddEdge(d * 2, u * 2);
// Appendix :
if (l && d && !r && !u)
AddEdge(l * 2, d * 2);
if (l && u && !r && !d)
AddEdge(l * 2 - 1, u * 2);
if (r && d && !l && !u)
AddEdge(r * 2, d * 2 - 1);
if (r && u && !l && !d)
AddEdge(r * 2 - 1, u * 2 - 1);
if (l && !r && !d && !u)
AddEdge(l * 2 - 1, l * 2);
if (r && !l && !d && !u)
AddEdge(r * 2 - 1, r * 2);
if (d && !l && !r && !u)
AddEdge(d * 2 - 1, d * 2);
if (u && !l && !r && !d)
AddEdge(u * 2 - 1, u * 2);
}
vector < pair < int , int > > Events;
for (int i = 1; i <= m; i ++)
if (A[V[i]].x == A[U[i]].x)
Events.push_back({A[V[i]].x, i});
sort(Events.begin(), Events.end());
deque < int > Dq;
memset(D, 63, sizeof(D));
for (auto event : Events)
{
int e = event.second;
if (M[e * 2 - 1])
continue;
D[e * 2 - 1] = 0;
Dq.push_back(e * 2 - 1);
while (Dq.size())
{
int v = Dq.front();
Dq.pop_front();
if (M[v])
continue;
M[v] = 1;
for (int u : Ad[v])
if (D[u] > D[v])
D[u] = D[v], Dq.push_front(u);
int u;
if (v & 1) u = v + 1;
else u = v - 1;
if (D[u] > D[v] + 1)
D[u] = D[v] + 1, Dq.push_back(u);
}
}
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:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
22 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
flood.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
24 | scanf("%d%d", &A[i].x, &A[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
25 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
flood.cpp:28:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | scanf("%d%d", &V[i], &U[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
13696 KB |
Output is correct |
| 2 |
Correct |
9 ms |
13696 KB |
Output is correct |
| 3 |
Correct |
10 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13696 KB |
Output is correct |
| 2 |
Correct |
10 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
13696 KB |
Output is correct |
| 2 |
Correct |
9 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
13696 KB |
Output is correct |
| 2 |
Correct |
10 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
13696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
16768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
25456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
26248 KB |
Output is correct |
| 2 |
Correct |
334 ms |
32316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
30060 KB |
Output is correct |
| 2 |
Correct |
325 ms |
32624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
307 ms |
31856 KB |
Output is correct |
| 2 |
Correct |
181 ms |
28168 KB |
Output is correct |
