| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291592 |
2020-09-05T14:05:03 Z |
Kastanda |
Flood (IOI07_flood) |
C++11 |
|
449 ms |
65540 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], P[N];
bitset < N * 4 > M;
pair < int , int > A[N];
vector < int > E[N];
vector < int > Ad[N * 4];
int Find(int v)
{
return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
v = Find(v);
u = Find(u);
if (v != u)
P[v] = u;
}
inline bool Connected(int v, int u)
{
v = (v + 1) / 2;
u = (u + 1) / 2;
return Find(V[v]) == Find(V[u]);
}
inline void AddEdge(int v, int u)
{
if (!Connected(v, u))
return ;
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)
*/
memset(P, -1, sizeof(P));
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);
Merge(V[i], U[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);
}
for (int w = 0; w <= 1; w ++)
{
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());
set < pair < pair < int , int > , int > > ST;
for (auto event : Events)
{
int e = event.second;
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);
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), it = ST.erase(it);
if (it != ST.end() && it->first.first < ry)
{
AddEdge(e * 2 - 1, it->second * 2);
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 = 1; i <= m; i ++)
swap(A[i].x, A[i].y);
}
deque < int > Dq;
memset(D, 63, sizeof(D));
for (int i = 1; i <= m * 2; i ++)
if ((int)Ad[i].size() == 0)
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 (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:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
flood.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%d%d", &A[i].x, &A[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
45 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
flood.cpp:48:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
48 | scanf("%d%d", &V[i], &U[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14080 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14080 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14080 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
16616 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
23076 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
21516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
28020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
373 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
