Submission #684059

#	Time	Username	Problem	Language	Result	Execution time	Memory
684059		piOOE	Simurgh (IOI17_simurgh)	C++17	100 / 100	939 ms	5148 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> p;

    DSU() = default;

    DSU(int n) : p(n) {
        iota(p.begin(), p.end(), 0);
    }

    int leader(int x) {
        while (x != p[x]) x = p[x] = p[p[x]];
        return x;
    }

    bool unite(int x, int y) {
        x = leader(x), y = leader(y);
        if (x == y) {
            return false;
        }
        p[y] = x;
        return true;
    }

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }
};

vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V) {
    const int m = U.size();
    vector<int> type(m, -1);

    vector idx(n, vector<int>(n, -1));
    for (int i = 0; i < m; ++i) {
        idx[U[i]][V[i]] = idx[V[i]][U[i]] = i;
    }

    DSU d1(n);
    vector<int> st, par(n, -1), tin(n, -1);
    vector<bool> in_st(m);


    int T = 0;
    auto dfs = [&](auto self, int v) -> void {
        tin[v] = T++;
        for (int to = 0; to < n; ++to) {
            if (tin[to] == -1 && idx[v][to] != -1) {
                par[to] = v;
                in_st[idx[v][to]] = true;
                st.push_back(idx[v][to]);
                self(self, to);
            }
        }
    };

    dfs(dfs, 0);

    auto path = [&](int x, int y) {
        if (tin[x] > tin[y]) {
            swap(x, y);
        }
        vector<int> ans;
        while (y != x) {
            ans.push_back(idx[y][par[y]]);
            y = par[y];
        }
        return ans;
    };

    const int init = count_common_roads(st);

    for (int i = 0; i < m; ++i) {
        if (!in_st[i]) {
            auto p = path(U[i], V[i]);
            sort(p.begin(), p.end());

            int done = -1, not_done = -1;
            for (int x: p) {
                if (type[x] != -1) {
                    done = x;
                } else {
                    not_done = x;
                }
            }

            if (done != -1) {
                if (not_done == -1) {
                    continue;
                }
                set<int> sp(st.begin(), st.end());
                sp.insert(i);

                sp.erase(done);
                int aim = count_common_roads(vector(sp.begin(), sp.end()));
                sp.insert(done);
                for (int x: p) {
                    if (type[x] == -1) {
                        sp.erase(x);
                        int now = count_common_roads(vector(sp.begin(), sp.end()));
                        sp.insert(x);
                        type[x] = type[done] ^ (now != aim);
                    }
                }
            } else {
                set<int> sp(st.begin(), st.end());
                sp.insert(i);

                int mx = init, mn = init;
                vector<pair<int, int>> save{{init, i}};
                for (int x: p) {
                    sp.erase(x);
                    int now = count_common_roads(vector(sp.begin(), sp.end()));
                    sp.insert(x);
                    mx = max(mx, now), mn = min(mn, now);
                    save.emplace_back(now, x);
                }

                for (auto [now, x]: save) {
                    if (mn == mx) {
                        type[x] = 0;
                    } else {
                        type[x] = now != mx;
                    }
                }
            }
        }
    }
    for (int i : st) {
        if (type[i] == -1) {
            type[i] = 1;
        }
    }

    auto howMany = [&](vector<int> a) {
        DSU d(n);
        for (int i: a) {
            assert(d.unite(U[i], V[i]));
        }
        int cnt = 0;
        for (int p : st) {
            if (d.unite(U[p], V[p])) {
                a.push_back(p);
                cnt += type[p];
            }
        }

        assert(a.size() == n - 1);
        return count_common_roads(a) - cnt;
    };

    for (int v = 0; v < n; ++v) {
        vector<int> need;
        for (int to = 0; to < n; ++to) {
            if (idx[v][to] != -1 && type[idx[v][to]] == -1) {
                need.push_back(idx[v][to]);
            }
        }

        auto solve = [&](auto self, vector<int> a, int cnt) -> void {
            if (cnt == 0) {
                for (int i : a) {
                    type[i] = 0;
                }
                return;
            }
            if (a.size() == 1) {
                type[a[0]] = 1;
                return;
            }
            vector<int> L(a.begin(), a.begin() + a.size() / 2);
            vector<int> R(a.begin() + a.size() / 2, a.end());
            int have = howMany(L);
            self(self, L, have);
            self(self, R, cnt - have);
        };
        solve(solve, need, howMany(need));
    }

    st.clear();
    for (int i = 0; i < m; ++i) {
        assert(type[i] != -1);
        if (type[i] == 1) {
            st.push_back(i);
        }
    }

    assert(st.size() == n - 1);

    return st;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In lambda function:
simurgh.cpp:152:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  152 |         assert(a.size() == n - 1);
      |                ~~~~~~~~~^~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:192:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  192 |     assert(st.size() == n - 1);
      |            ~~~~~~~~~~^~~~~~~~

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