Submission #536039

#	Time	Username	Problem	Language	Result	Execution time	Memory
536039		KoD	Simurgh (IOI17_simurgh)	C++17	0 / 100	0 ms	212 KiB

simurgh

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

template <class F> struct rec_lambda : private F {
    explicit rec_lambda(F&& f) : F(forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, forward<Args>(args)...);
    }
};

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
    const int M = U.size();
    vector<vector<int>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[U[i]].push_back(i);
        graph[V[i]].push_back(i);
    }
    const auto dst = [&](const int u, const int e) {
        return U[e] ^ V[e] ^ u;
    };
    vector<int> depth(N), pedge(N);
    vector<char> is_tree(M);
    depth[0] = 1;
    rec_lambda([&](auto&& dfs, const int u) -> void {
        for (const int e : graph[u]) {
            const int v = dst(u, e);
            if (depth[v] == 0) {
                depth[v] = depth[u] + 1;
                pedge[v] = e;
                is_tree[e] = true;
                dfs(v);
            }
        }
    })(0);
    for (int i = 0; i < M; ++i) {
        if (depth[U[i]] > depth[V[i]]) swap(U[i], V[i]);
    }
    vector<int> ask_list;
    ask_list.reserve(N - 1);
    const auto ask_tree = [&] {
        ask_list.clear();
        for (int i = 0; i < M; ++i) {
            if (is_tree[i]) ask_list.push_back(i);
        }
        return count_common_roads(ask_list);
    }; 
    const auto ask_swapped = [&](const int e, const int f) {
        is_tree[e] = true;
        is_tree[f] = false;
        const int ret = ask_tree();
        is_tree[e] = false;
        is_tree[f] = true;
        return ret;
    };
    const int base = ask_tree();
    vector<int> type(M, -1);
    for (int e = 0; e < M; ++e) {
        if (is_tree[e]) continue;
        vector<int> done, tbd;
        for (int u = V[e]; u != U[e]; u = dst(u, pedge[u])) {
            const int f = pedge[u];
            (type[f] >= 0 ? done : tbd).push_back(f); 
        }
        const int m = tbd.size();
        if (m == 0) continue;
        vector<int> dif(m);
        for (int i = 0; i < m; ++i) {
            dif[i] = ask_swapped(e, tbd[i]) - base;
        }
        if (done.empty()) {
            for (const int x : dif) {
                if (x == 1) type[e] = 1;
                if (x == -1) type[e] = 0;
            }
            if (type[e] == -1) type[e] = 0;
        } else {
            const int f = done.front();
            type[e] = type[f] + ask_swapped(e, f) - base;
        }
        for (int i = 0; i < m; ++i) {
            type[tbd[i]] = type[e] - dif[i];
        }
    }
    for (int i = 0; i < M; ++i) {
        if (is_tree[i] and type[i] == -1) type[i] = 1;
    }
    vector<char> used(N);
    const auto count = [&](const int pivot, vector<int> list) {
        if (list.empty()) return 0;
        ask_list.clear();
        for (const int e : list) {
            ask_list.push_back(e);
            if (U[e] == pivot) {
                used[U[pedge[V[e]]]] = true;
            } else {
                used[V[e]] = true;
            }
        }
        int subt = 0;
        for (int u = 1; u < N; ++u) {
            const int e = pedge[u];
            if (!used[U[e]]) {
                subt += type[e];
                ask_list.push_back(e); 
            }
        }
        for (const int e : list) {
            if (U[e] == pivot) {
                used[U[pedge[V[e]]]] = false;
            } else {
                used[V[e]] = false;
            }
        }
        return count_common_roads(ask_list) - subt;
    };
    for (int pivot = 0; pivot < N; ++pivot) {
        vector<int> list;
        for (const int e : graph[pivot]) {
            if (type[e] == -1) list.push_back(e);
        }
        rec_lambda([&](auto&& dfs, const int l, const int r) -> void {
            if (count(pivot, vector<int>(list.begin() + l, list.begin() + r)) == 0) return;
            if (l + 1 == r) {
                type[list[l]] = 1;
            } else {
                const int m = (l + r) / 2;
                dfs(l, m);
                dfs(m, r);
            }
        })(0, list.size());
        for (const int e : list) {
            if (type[e] == -1) type[e] = 0;
        }
    }
    vector<int> ret;
    ret.reserve(N - 1);
    for (int i = 0; i < M; ++i) {
        if (type[i] == 1) ret.push_back(i);
    }
    return ret;
}

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