| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 819905 |
2023-08-10T15:18:15 Z |
canadavid1 |
Flood (IOI07_flood) |
C++14 |
|
119 ms |
11856 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
using i32 = int32_t;
using u32 = uint32_t;
/*
Ideas
all edges that are the same distance (in min number of edges to cross) from the border on both sides
make the dual graph
do a topological sort
remove redundant edges
subtask 1: just flood fill
ODD INTERSECTIONS (1 OR 3 WALLS) REQUIRED
needs to be on path from one odd intersection to another to be preserved
traverse along the edge (start with the leftmost vertex), giving a (not necessarily convex) hull
if ever end up with a 1-vertex, backtrack once and remove the edge (it will be preserved)
remove all the edges along the path
repeat
might need to special-case when there is only a single edge left in the component
*/
enum dir {
YPLUS=0,
XPLUS,
YMINUS,
XMINUS
};
u32 ct(const array<i32,4>& v)
{
return (v[0]!=-1) + (v[1]!=-1) + (v[2]!=-1) + (v[3]!=-1);
}
u32 child(u32 i,const array<i32,4>&v,int idx=0)
{
idx--;
for(;i>=0;i--) do idx=(idx+1)%4; while(v[idx]==-1);
// returns the i'th neighbour
return idx;
}
signed main()
{
i32 N;
cin >> N;
vector<pair<u32, u32>> points(N);
vector<array<i32, 4>> neigh(N, array<i32, 4>{-1,-1,-1,-1});
vector<array<u32, 4>> neighid(N,array<u32,4>{});
vector<i32> id(N);
iota(all(id), 0);
for (auto&& i : points)
cin >> i.first >> i.second;
sort(all(id), [&](auto a, auto b)
{ return points[a] < points[b]; });
i32 W;
cin >> W;
for (int i = 1; i <= W; i++)
{
int A,B;
cin >> A >> B;
A--;B--;
if(points[A] > points[B]) std::swap(A,B);
if (points[A].first != points[B].first)
{
// horizontal wall
neigh[A][XPLUS] = B;
neigh[B][XMINUS] = A;
neighid[A][XPLUS] = i;
neighid[B][XMINUS] = i;
}
else
{
// vertical wall
neigh[A][YPLUS] = B;
neigh[B][YMINUS] = A;
neighid[A][YPLUS] = i;
neighid[B][YMINUS] = i;
}
}
vector<u32> out;
for(auto point : id)
{
if (ct(neigh[point])==0) continue;
if(ct(neigh[point])==1)
{
// just remove the point
int idx = 0;
while(neigh[point][idx]==-1) idx++;
out.push_back(neighid[point][idx]);
auto n = neigh[point][idx];
neigh[n][(idx+2)%4] = -1;
neigh[point][idx] = -1;
continue;
}
vector<u32> visit; // the nodes visited
// traverse around the border
int idx = 0;
while(neigh[point][idx]==-1) idx++;
visit.push_back(point);
visit.push_back(neigh[point][idx]);
while(visit.back() != point)
{
if(ct(neigh[visit.back()]) == 1)
{
idx = 0;
while(neigh[visit.back()][idx]!=visit[visit.size()-2]) idx++;
out.push_back(neighid[visit.back()][idx]);
// remove edge
neigh[visit.back()][idx] = -1;
visit.pop_back();
neigh[visit.back()][(idx+2)%4] = -1;
continue;
}
idx = 0;
while(neigh[visit.back()][idx]!=visit[visit.size()-2]) idx++;
// find next node to visit
do idx = (idx+1)%4; while (neigh[visit.back()][idx]==-1);
visit.push_back(neigh[visit.back()][idx]);
}
for (auto i = 0; i < visit.size()-1; i++)
{
// remove edge between visit[i] and visit[i+1]
idx = 0;
while(neigh[visit[i]][idx]!=visit[i+1]) idx++;
neigh[visit[i]][idx] = -1;
neigh[visit[i+1]][(idx+2)%4] = -1;
}
}
cout << out.size() << "\n";
for(auto i : out) cout << i << "\n";
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:107:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<unsigned int>, unsigned int>::value_type' {aka 'unsigned int'} and 'int' [-Wsign-compare]
107 | while(visit.back() != point)
| ~~~~~~~~~~~~~^~~~~~~~
flood.cpp:112:43: warning: comparison of integer expressions of different signedness: 'std::array<int, 4>::value_type' {aka 'int'} and '__gnu_cxx::__alloc_traits<std::allocator<unsigned int>, unsigned int>::value_type' {aka 'unsigned int'} [-Wsign-compare]
112 | while(neigh[visit.back()][idx]!=visit[visit.size()-2]) idx++;
flood.cpp:121:43: warning: comparison of integer expressions of different signedness: 'std::array<int, 4>::value_type' {aka 'int'} and '__gnu_cxx::__alloc_traits<std::allocator<unsigned int>, unsigned int>::value_type' {aka 'unsigned int'} [-Wsign-compare]
121 | while(neigh[visit.back()][idx]!=visit[visit.size()-2]) idx++;
flood.cpp:126:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (auto i = 0; i < visit.size()-1; i++)
| ~~^~~~~~~~~~~~~~~~
flood.cpp:130:39: warning: comparison of integer expressions of different signedness: 'std::array<int, 4>::value_type' {aka 'int'} and '__gnu_cxx::__alloc_traits<std::allocator<unsigned int>, unsigned int>::value_type' {aka 'unsigned int'} [-Wsign-compare]
130 | while(neigh[visit[i]][idx]!=visit[i+1]) idx++;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
2996 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
9804 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
6344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
11564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
119 ms |
11856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
