Submission #685151

#	Time	Username	Problem	Language	Result	Execution time	Memory
685151		finn__	Flood (IOI07_flood)	C++17	100 / 100	230 ms	19176 KiB

flood

#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();)
        if (it->is_isolated())
            it = s.erase(it);
        else
            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 (stderr)

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;
      |                                                                ~~~~~~~^~~~~

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