| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 685251 |
2023-01-23T18:34:56 Z |
finn__ |
Flood (IOI07_flood) |
C++17 |
|
234 ms |
28428 KB |
#include <bits/stdc++.h>
using namespace std;
struct Point
{
unsigned x, y;
unsigned adj[4], ind[4];
unsigned go(unsigned last_move) const
{
for (unsigned j = 0; j < 4; j++)
if (adj[(last_move + 5 - j) % 4] != UINT_MAX)
return (last_move + 5 - j) % 4;
}
bool dominates(Point const &q) const { return x >= q.x && y >= q.y; }
};
vector<Point> points;
bool edge_compare(pair<unsigned, unsigned> const &a, pair<unsigned, unsigned> const &b)
{
return points[a.first].x < points[b.first].x;
}
int main()
{
size_t n;
cin >> n;
points = vector<Point>(n);
for (Point &p : points)
{
cin >> p.x >> p.y;
memset(p.adj, 255, 4 * sizeof *p.adj);
}
size_t w;
cin >> w;
vector<pair<unsigned, unsigned>> edges;
for (size_t i = 0; i < w; i++)
{
unsigned a, b;
cin >> a >> b;
a--, b--;
Point &u = points[a];
Point &v = points[b];
if (u.x == v.x)
{
if (u.y < v.y)
{
u.adj[0] = b, v.adj[2] = a, u.ind[0] = v.ind[2] = i;
edges.emplace_back(a, 2);
edges.emplace_back(b, 0);
}
else
{
u.adj[2] = b, v.adj[0] = a, u.ind[2] = v.ind[0] = i;
edges.emplace_back(a, 0);
edges.emplace_back(b, 2);
}
}
else
{
if (u.x < v.x)
{
u.adj[1] = b, v.adj[3] = a, u.ind[1] = v.ind[3] = i;
edges.emplace_back(a, 3);
edges.emplace_back(b, 1);
}
else
{
u.adj[3] = b, v.adj[1] = a, u.ind[3] = v.ind[1] = i;
edges.emplace_back(a, 1);
edges.emplace_back(b, 3);
}
}
}
sort(edges.begin(), edges.end(), edge_compare);
vector<set<unsigned>> g;
vector<array<unsigned, 2>> dual_edges(w, {UINT_MAX, UINT_MAX});
vector<array<unsigned, 2>> used_dir(w, {UINT_MAX, UINT_MAX});
for (size_t i = 0; i < edges.size(); i++)
{
auto const [z, dir] = edges[i];
if (used_dir[points[z].ind[(dir + 2) % 4]][0] == dir ||
used_dir[points[z].ind[(dir + 2) % 4]][1] == dir)
continue;
unsigned u = z, d = dir, new_node = g.size();
g.push_back({});
do // Trace the dual node adjacent to one side.
{
unsigned const e = points[u].go(d);
d = e;
if (dual_edges[points[u].ind[e]][0] == UINT_MAX)
{
dual_edges[points[u].ind[e]][0] = new_node;
used_dir[points[u].ind[e]][0] = e;
}
else
{
dual_edges[points[u].ind[e]][1] = new_node;
used_dir[points[u].ind[e]][1] = e;
}
u = points[u].adj[e];
} while (u != z);
}
for (auto const &a : dual_edges)
g[a[0]].insert(a[1]), g[a[1]].insert(a[0]);
vector<unsigned> t(g.size());
queue<unsigned> q;
vector<bool> visited(g.size(), 0);
q.push(0);
t[0] = 0;
visited[0] = 1;
while (!q.empty())
{
auto const u = q.front();
q.pop();
for (unsigned const &v : g[u])
if (!visited[v])
{
visited[v] = 1;
t[v] = t[u] + 1;
q.push(v);
}
}
unsigned num_standing = 0;
for (size_t i = 0; i < w; i++)
if (t[dual_edges[i][0]] == t[dual_edges[i][1]])
num_standing++;
cout << num_standing << '\n';
for (size_t i = 0; i < w; i++)
if (t[dual_edges[i][0]] == t[dual_edges[i][1]])
cout << i + 1 << '\n';
}
Compilation message
flood.cpp: In member function 'unsigned int Point::go(unsigned int) const':
flood.cpp:14:5: warning: control reaches end of non-void function [-Wreturn-type]
14 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 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 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
412 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
4292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
9048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
142 ms |
21880 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
21932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
234 ms |
28428 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
