| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 685145 |
2023-01-23T15:11:04 Z |
finn__ |
Flood (IOI07_flood) |
C++17 |
|
239 ms |
21304 KB |
#include <bits/stdc++.h>
using namespace std;
struct Node
{
unsigned adj[4], adj_i[4]; // up, right, down, left
unsigned x, y, i;
Node() {}
Node(unsigned _x, unsigned _y) { x = _x, y = _y; }
bool operator<(Node const &z) const
{
return x == z.x ? y < z.y : x < z.x;
}
unsigned successor(unsigned last) const
{
for (unsigned j = 0; j < 4; j++)
if (adj[(last + 5 + j) % 4] != -1)
return (last + 5 + j) % 4;
return last;
}
bool is_isolated() const
{
return adj[0] == -1 && adj[1] == -1 && adj[2] == -1 && adj[3] == -1;
}
bool operator!=(Node const &z) const { return x != z.x || y != z.y; }
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n;
cin >> n;
vector<Node> nodes(n);
for (size_t i = 0; i < n; i++)
{
cin >> nodes[i].x >> nodes[i].y;
memset(nodes[i].adj, 255, 4 * sizeof *nodes[i].adj);
nodes[i].i = i;
}
size_t w;
cin >> w;
for (size_t i = 0; i < w; i++)
{
unsigned a, b;
cin >> a >> b;
a--, b--;
Node &u = nodes[a];
Node &v = nodes[b];
if (u.x == v.x)
{
if (u.y < v.y)
u.adj[0] = b, v.adj[2] = a, u.adj_i[0] = v.adj_i[2] = i;
else
u.adj[2] = b, v.adj[0] = a, u.adj_i[2] = v.adj_i[0] = i;
}
else
{
if (u.x < v.x)
u.adj[1] = b, v.adj[3] = a, u.adj_i[1] = v.adj_i[3] = i;
else
u.adj[3] = b, v.adj[1] = a, u.adj_i[3] = v.adj_i[1] = i;
}
}
set<Node> s(nodes.begin(), nodes.end());
vector<bool> is_standing(w, 0), was_traversed(w, 0);
for (auto it = s.begin(); it != s.end(); it++)
if (it->is_isolated())
it = s.erase(it);
while (!s.empty())
{
Node u = *s.begin(), v = *s.begin();
unsigned last = -1;
do // Reset traversal counts of edges.
{
was_traversed[v.adj_i[v.successor(last)]] = 0;
unsigned _last = (v.successor(last) + 2) % 4;
v = nodes[v.adj[v.successor(last)]];
last = _last;
} while (u != v);
v = u, last = -1;
do // Mark edges traversed twice as standing.
{
if (was_traversed[v.adj_i[v.successor(last)]])
is_standing[v.adj_i[v.successor(last)]] = 1;
was_traversed[v.adj_i[v.successor(last)]] = 1;
unsigned _last = (v.successor(last) + 2) % 4;
v = nodes[v.adj[v.successor(last)]];
last = _last;
} while (u != v);
v = u, last = -1;
queue<pair<pair<unsigned, unsigned>, unsigned>> q;
do // Remove traversed walls and dead nodes.
{
q.emplace(make_pair(v.x, v.y), v.successor(last));
q.emplace(make_pair(nodes[v.adj[v.successor(last)]].x, nodes[v.adj[v.successor(last)]].y), (v.successor(last) + 2) % 4);
unsigned _last = (v.successor(last) + 2) % 4;
v = nodes[v.adj[v.successor(last)]];
last = _last;
} while (u != v);
while (!q.empty())
{
Node z = *s.find(Node(q.front().first.first, q.front().first.second));
if (z != Node(q.front().first.first, q.front().first.second))
{
q.pop();
continue;
}
z.adj[q.front().second] = -1;
s.erase(z);
if (!z.is_isolated())
s.insert(z);
nodes[z.i] = z;
q.pop();
}
}
unsigned num_standing = 0;
for (unsigned i = 0; i < w; i++)
num_standing += is_standing[i];
cout << num_standing << '\n';
for (unsigned i = 0; i < w; i++)
if (is_standing[i])
cout << i + 1 << '\n';
}
Compilation message
flood.cpp: In member function 'unsigned int Node::successor(unsigned int) const':
flood.cpp:21:41: warning: comparison of integer expressions of different signedness: 'const unsigned int' and 'int' [-Wsign-compare]
21 | if (adj[(last + 5 + j) % 4] != -1)
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
flood.cpp: In member function 'bool Node::is_isolated() const':
flood.cpp:28:23: warning: comparison of integer expressions of different signedness: 'const unsigned int' and 'int' [-Wsign-compare]
28 | return adj[0] == -1 && adj[1] == -1 && adj[2] == -1 && adj[3] == -1;
| ~~~~~~~^~~~~
flood.cpp:28:39: warning: comparison of integer expressions of different signedness: 'const unsigned int' and 'int' [-Wsign-compare]
28 | return adj[0] == -1 && adj[1] == -1 && adj[2] == -1 && adj[3] == -1;
| ~~~~~~~^~~~~
flood.cpp:28:55: warning: comparison of integer expressions of different signedness: 'const unsigned int' and 'int' [-Wsign-compare]
28 | return adj[0] == -1 && adj[1] == -1 && adj[2] == -1 && adj[3] == -1;
| ~~~~~~~^~~~~
flood.cpp:28:71: warning: comparison of integer expressions of different signedness: 'const unsigned int' and 'int' [-Wsign-compare]
28 | return adj[0] == -1 && adj[1] == -1 && adj[2] == -1 && adj[3] == -1;
| ~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 7 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
7648 KB |
Execution killed with signal 7 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
14024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
14920 KB |
Output is correct |
| 2 |
Correct |
239 ms |
17236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
16852 KB |
Output is correct |
| 2 |
Correct |
224 ms |
17464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
236 ms |
17168 KB |
Output is correct |
| 2 |
Correct |
164 ms |
21304 KB |
Output is correct |
