제출 #790581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790581		skittles1412	Simurgh (IOI17_simurgh)	C++17	51 / 100	263 ms	31252 KiB

simurgh

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

int count_common_roads(const vector<int>& r);

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    out << "]";
    return out;
}

struct Q {
    map<vector<int>, int> cache;

    int query(vector<int> arr) {
        sort(begin(arr), end(arr));
        auto [it, inserted] = cache.emplace(arr, 0);
        if (inserted) {
            it->second = count_common_roads(arr);
        }
        return it->second;
    }
} Q;

struct DSU {
    vector<int> p;

    DSU(int n) : p(n, -1) {}

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

    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return false;
        }
        if (p[u] < p[v]) {
            swap(u, v);
        }
        p[v] += p[u];
        p[u] = v;
        return true;
    }
};

void to_comps(int n,
              int ign_u,
              const vector<int>& e_u,
              const vector<int>& e_v,
              vector<vector<int>>& out,
              vector<int>& st) {
    DSU dsu(n);
    for (int i = 0; i < sz(e_u); i++) {
        int u = e_u[i], v = e_v[i];
        if (u == ign_u || v == ign_u) {
            continue;
        }
        if (dsu.merge(u, v)) {
            st.push_back(i);
        }
    }
    out.resize(n);
    for (int i = 0; i < n; i++) {
        out[dsu.find(i)].push_back(i);
    }
    out.erase(remove_if(begin(out), end(out),
                        [&](const auto& c) -> bool {
                            return !sz(c) || (sz(c) == 1 && c[0] == ign_u);
                        }),
              out.end());
}

vector<int> find_roads(int n, vector<int> e_u, vector<int> e_v) {
    int m = sz(e_u);
    vector<pair<int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int u = e_u[i], v = e_v[i];
        graph[u].emplace_back(v, i);
        graph[v].emplace_back(u, i);
    }

    bool e_ans[m] {};
    vector<int> ans, st;
    vector<vector<int>> comps;

    for (int cu = 0; cu < n; cu++) {
        comps.clear();
        st.clear();

        auto decided = [&](int ei) -> bool {
            return e_u[ei] < cu || e_v[ei] < cu;
        };

        to_comps(n, cu, e_u, e_v, comps, st);
        int comp_ind[n];
        for (int i = 0; i < sz(comps); i++) {
            assert(sz(comps[i]));
            for (auto& a : comps[i]) {
                dbg(a);
                comp_ind[a] = i;
            }
            dbg("---");
        }
        vector<int> comp_e[sz(comps)];
        for (auto& [v, ei] : graph[cu]) {
            comp_e[comp_ind[v]].push_back(ei);
        }
        dbg(cu, sz(comps));

        for (int i = 0; i < sz(comps); i++) {
            auto cst = st;
            for (int j = 0; j < sz(comps); j++) {
                if (i == j) {
                    continue;
                }
                cst.push_back(comp_e[j][0]);
            }

            vector<int> to_decide;
            for (auto& a : comp_e[i]) {
                if (!decided(a)) {
                    to_decide.push_back(a);
                }
            }

            if (!sz(to_decide)) {
                continue;
            }

            int rep = -1;
            for (auto& a : comp_e[i]) {
                if (decided(a)) {
                    rep = e_ans[a];
                    to_decide.push_back(a);
                    break;
                }
            }

            if (sz(to_decide) == 1) {
                ans.push_back(to_decide[0]);
                continue;
            }

            vector<int> dqueries;
            for (auto& a : to_decide) {
                cst.push_back(a);
                dqueries.push_back(Q.query(cst));
                cst.pop_back();
            }

            int cmn = *min_element(begin(dqueries), end(dqueries)),
                cmx = *max_element(begin(dqueries), end(dqueries));

            if (cmn == cmx) {
                if (!rep) {
                    continue;
                }
            }
            dbg(to_decide, dqueries);
            for (int j = 0; j < sz(to_decide); j++) {
                if (dqueries[j] == cmx && !decided(to_decide[j])) {
                    dbg(to_decide[j]);
                    e_ans[to_decide[j]] = true;
                    ans.push_back(to_decide[j]);
                }
            }
        }
    }

    dbg(ans);

    return ans;
}

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