Submission #832078

#	Time	Username	Problem	Language	Result	Execution time	Memory
832078		finn__	Simurgh (IOI17_simurgh)	C++17	70 / 100	86 ms	7524 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

namespace quadratic
{
    constexpr size_t N = 240;

    vector<pair<int, int>> g[N];
    int adj[N][N];
    bitset<N *(N - 1) / 2> checked, is_in;

    vector<int> solve(int n, vector<int> u, vector<int> v)
    {
        memset(adj, 255, sizeof adj);
        for (int i = 0; i < u.size(); ++i)
            g[u[i]].emplace_back(v[i], i), g[v[i]].emplace_back(u[i], i), adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;
        vector<int> ans;

        for (int i = 0; i < n; ++i)
        {
            vector<vector<int>> bccs, bcc_trees;
            vector<int> edge_to_bcc;
            bitset<N> visited;
            visited[i] = 1;

            for (auto const &[z, j] : g[i])
                if (!visited[z])
                {
                    queue<int> q({z});
                    visited[z] = 1;
                    edge_to_bcc.push_back(j);
                    vector<int> nodes, edges;

                    while (!q.empty())
                    {
                        int x = q.front();
                        nodes.push_back(x);
                        q.pop();
                        for (auto const &[y, i] : g[x])
                            if (!visited[y])
                            {
                                edges.push_back(i);
                                q.push(y);
                                visited[y] = 1;
                            }
                    }

                    bccs.push_back(nodes);
                    bcc_trees.push_back(edges);
                }

            for (size_t j = 0; j < bccs.size(); ++j)
            {
                vector<int> spanning_tree;
                for (size_t k = 0; k < bccs.size(); ++k)
                {
                    spanning_tree.insert(spanning_tree.end(), bcc_trees[k].begin(), bcc_trees[k].end());
                    if (k != j)
                        spanning_tree.push_back(edge_to_bcc[k]);
                }

                for (auto const &x : bccs[j])
                    if (adj[i][x] != -1)
                    {
                        spanning_tree.push_back(adj[i][x]);
                        break;
                    }

                int in_overlap = count_common_roads(spanning_tree), out_overlap = in_overlap;
                vector<int> in;
                bool skipped = 0, know_in = 0;
                for (auto const &x : bccs[j])
                    if (adj[i][x] != -1)
                    {
                        if (!skipped)
                        {
                            checked[adj[i][x]] = 1;
                            in.push_back(adj[i][x]);
                            skipped = 1;
                            continue;
                        }

                        if (checked[adj[i][x]] && know_in)
                            continue;

                        spanning_tree.pop_back();
                        spanning_tree.push_back(adj[i][x]);
                        int y = count_common_roads(spanning_tree);
                        if (!know_in)
                        {
                            if (checked[adj[i][x]])
                            {
                                know_in = 1;
                                if (is_in[adj[i][x]])
                                {
                                    if (in_overlap < y)
                                        in.clear(), ++in_overlap;
                                    else
                                        --out_overlap;
                                }
                                else
                                {
                                    if (in_overlap == y)
                                        in.clear(), ++in_overlap;
                                    else
                                        --out_overlap;
                                }
                            }
                            if (y == in_overlap)
                                in.push_back(adj[i][x]);
                            else if (y < in_overlap)
                            {
                                out_overlap--;
                                know_in = 1;
                            }
                            else if (y > in_overlap)
                            {
                                know_in = 1;
                                in.clear();
                                in_overlap++;
                                in.push_back(adj[i][x]);
                            }
                        }
                        else if (y == in_overlap)
                            in.push_back(adj[i][x]);

                        checked[adj[i][x]] = 1;
                    }

                ans.insert(ans.end(), in.begin(), in.end());
                for (auto const &j : in)
                    is_in[j] = 1;
            }
        }

        sort(ans.begin(), ans.end());
        ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
        return ans;
    }
};

template <size_t N>
struct dsu
{
    int p[N];

    int repr(int u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }

    bool merge(int u, int v)
    {
        u = repr(u), v = repr(v);
        if (u == v)
            return 0;
        if (p[u] > p[v])
            swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return 1;
    }

    int set_size(int u) { return -p[repr(u)]; }

    void reset() { memset(p, 255, sizeof p); }
};

namespace nlogn
{
    constexpr size_t N = 500;

    int adj[N][N], degree[N];
    bitset<N *(N - 1) / 2> is_in, removed;
    dsu<N> d;

    vector<int> solve(int n, vector<int> u, vector<int> v)
    {
        if (n == 2)
            return {0};
        for (int i = 0; i < u.size(); ++i)
            adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;

        auto query_forest = [&](vector<int> forest)
        {
            d.reset();
            for (int i : forest)
                d.merge(u[i], v[i]);
            int ans = 0;
            for (int i = 0; i + 1 < n; ++i)
                if (d.merge(i, i + 1))
                {
                    if (is_in[adj[i][i + 1]])
                        --ans;
                    forest.push_back(adj[i][i + 1]);
                }
            return ans + count_common_roads(forest);
        };

        auto check_edge = [&](int u, int v)
        {
            int w = 0;
            while (w == u || w == v)
                ++w;
            vector<int> spanning_tree;
            for (int i = 0; i < n; ++i)
                if (i != u && i != v && i != w)
                    spanning_tree.push_back(adj[u][i]);

            spanning_tree.push_back(adj[u][v]);
            spanning_tree.push_back(adj[v][w]);
            int a = count_common_roads(spanning_tree);
            spanning_tree[spanning_tree.size() - 2] = adj[w][u];
            int b = count_common_roads(spanning_tree);
            spanning_tree[spanning_tree.size() - 1] = adj[u][v];
            int c = count_common_roads(spanning_tree);
            return max(a, c) > b;
        };

        for (int i = 0; i + 1 < n; ++i)
            is_in[adj[i][i + 1]] = check_edge(i, i + 1);
        for (int i = 0; i < n; ++i)
        {
            vector<int> spanning_tree;
            for (int j = 0; j < n; ++j)
                if (i != j)
                    spanning_tree.push_back(adj[i][j]);
            degree[i] = count_common_roads(spanning_tree);
        }

        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1)
                q.push(i);

        vector<int> ans;
        while (ans.size() != n - 1)
        {
            int x = q.front();
            q.pop();

            int a = 0, b = n - 1;
            while (a < b)
            {
                int mid = (a + b) / 2;
                vector<int> forest;
                for (int j = 0; j <= mid; ++j)
                    if (j != x && !removed[adj[x][j]])
                        forest.push_back(adj[x][j]);
                if (query_forest(forest))
                    b = mid;
                else
                    a = mid + 1;
            }

            removed[adj[x][a]] = 1;
            ans.push_back(adj[a][x]);

            degree[a]--;
            if (degree[a] == 1)
                q.push(a);
        }

        return ans;
    }
};

vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
    if (u.size() != n * (n - 1) / 2)
        return quadratic::solve(n, u, v);
    else
        return nlogn::solve(n, u, v);
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> quadratic::solve(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:16:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (int i = 0; i < u.size(); ++i)
      |                         ~~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> nlogn::solve(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:179:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         for (int i = 0; i < u.size(); ++i)
      |                         ~~^~~~~~~~~~
simurgh.cpp:235:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  235 |         while (ans.size() != n - 1)
      |                ~~~~~~~~~~~^~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:268:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  268 |     if (u.size() != n * (n - 1) / 2)
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30