Submission #819905

#	Time	Username	Problem	Language	Result	Execution time	Memory
819905		canadavid1	Flood (IOI07_flood)	C++14	10 / 100	119 ms	11856 KiB

flood

#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 (stderr)

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++;

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9