Submission #685251

#	Time	Username	Problem	Language	Result	Execution time	Memory
685251		finn__	Flood (IOI07_flood)	C++17	23 / 100	234 ms	28428 KiB

flood

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

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 |     }
      |     ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 3 / 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