Submission #708552

#	Time	Username	Problem	Language	Result	Execution time	Memory
708552		jophyyjh	Simurgh (IOI17_simurgh)	C++14	0 / 100	1 ms	340 KiB

simurgh

/**
 * [S1-3] Well, it's not that difficult to come up with a solution for [S3]. Here,
 *      we have 1 query for each edge. We iterate through every node u, and let E(u)
 *      be the set of edges incident to u. We find an arbitrary spanning forest with
 *      the remaining edges. Assuming that the forest is in fact a tree, then we can
 *      iterate through every edge of E(u), adding it to the pre-built forest/tree.
 *      It's easy to see that every time a spanning tree of the whole graph is
 *      obtained, which means we can determine what edges of E(u) are actually in
 *      the hidden tree.
 *      Finally, the pre-built forest may not be a tree, so a bit more work is
 *      needed. Unfortunately, I have also written a quite ugly piece of impl.
 * [S4] Ask E(u), then the result would be deg(u). After noticing this, I realized
 *      we can determine by tree starting from its leaves. As a leaf only has 1
 *      neighbour, we can use binary search to find that neighbour. Iteratively
 *      finding all such edges is a possible solution.
 * 
 * Steps needed:    n^2 / 2 for general graphs, n * log_2(n) for complete graphs
 * Implementation 1                 (Solves [S1-3] (bound nearly tight), [S4])
*/

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

typedef std::vector<int>	vec;

// A disjoint set union structure which supports assigning an int value to each set.
struct DSU {
    int n;
    vec parent, size, values;
    DSU(int _n) {
        n = _n;
        parent.resize(n);
        size.resize(n);
        values.assign(n, -1);
        for (int k = 0; k < n; k++)
            parent[k] = k, size[k] = 1;
    }
    inline int find(int k) {
        if (parent[k] == k)
            return k;
        return parent[k] = find(parent[k]);
    }
    bool merge(int a, int b) {
        a = find(a), b = find(b);
        if (a == b)
            return false;
        if (size[b] > size[a])
            std::swap(a, b);
        parent[b] = a, size[a] += size[b];
        return true;
    }
    inline void set_val(int k, int value)   { values[find(k)] = value; }
    inline int get_val(int k)   { return values[find(k)]; }
};


vec square(int n, int m, const std::vector<vec>& graph) {
    vec is_ans(m, -1);      // -1: unknown
    for (int c = 0; c < n; c++) {
        DSU dsu(n);         // #value_of_set = #pos_of_repr_in_ask[]
        int deg = 0;
        vec ask;
        for (int neighb1 = 0; neighb1 < n; neighb1++) {
            if (neighb1 == c)
                continue;
            deg++;
            for (int neighb2 = 0; neighb2 < n; neighb2++) {
                if (neighb2 == c || graph[neighb1][neighb2] == -1)
                    continue;
                if (dsu.merge(neighb1, neighb2))
                    ask.push_back(graph[neighb1][neighb2]);
            }
        }
        for (int neighb = 0; neighb < n; neighb++) {
            if (graph[c][neighb] != -1 && dsu.get_val(neighb) == -1) {
                dsu.set_val(neighb, ask.size());
                ask.push_back(graph[c][neighb]);
            }
        }
        assert(int(ask.size()) == n - 1);
        for (int neighb = 0; neighb < n; neighb++) {
            if (graph[c][neighb] == -1)
                continue;
            int& base = is_ans[ask[dsu.get_val(neighb)]];
            base = (base == -1 ? 1 : base);
        }
        int base_num = count_common_roads(ask);
        vec result(deg);    // Results from count_common_roads()
        for (int neighb = 0, l = 0; neighb < n; neighb++) {
            int edge_idx = graph[neighb][c];
            if (edge_idx == -1)
                continue;
            if (is_ans[edge_idx] != -1)
                continue;
            int pos = dsu.get_val(neighb), original = ask[pos];
            ask[pos] = edge_idx;
            int switched_num = count_common_roads(ask);
            result[l++] = switched_num;
            if (switched_num > base_num)
                is_ans[edge_idx] = 1, is_ans[original] = 0;
            ask[pos] = original;
        }
        for (int neighb = 0, l = 0; neighb < n; neighb++) {
            int idx = graph[neighb][c];
            if (idx == -1)
                continue;
            if (is_ans[idx] != -1)
                continue;
            int rep = ask[dsu.get_val(neighb)];
            is_ans[idx] = (result[l++] != base_num ? 1 - is_ans[rep] : is_ans[rep]);
        }
    }
    vec ans;
    for (int k = 0; k < m; k++) {
        assert(is_ans[k] != -1);
        if (is_ans[k] == 1)
            ans.push_back(k);
    }
    assert(int(ans.size()) == n - 1);
    return ans;
}

vec complete(int n, const std::vector<vec>& graph) {
    vec deg(n, 0);
    std::queue<int> leaves;
    for (int k = 0; k < n; k++) {
        vec ask;
        for (int neighb = 0; neighb < n; neighb++) {
            if (neighb != k)
                ask.push_back(graph[neighb][k]);
        }
        deg[k] = count_common_roads(ask);
        if (deg[k] == 0)
            leaves.push(k);
    }
    vec ans;
    std::vector<bool> active(n, true);
    while (!leaves.empty()) {
        int l = leaves.front();
        leaves.pop();
        active[l] = false;
        vec remains;
        for (int k = 0; k < n; k++) {
            if (active[k])
                remains.push_back(k);
        }
        int a = 0, b = remains.size() - 1;
        while (a < b) {
            vec ask = ans;
            // IDK
            int half = (b - a + 1) / 2;
            for (int k = a; k < a + half; k++)
                ask.push_back(graph[remains[k]][remains[k + half]]);
            // IDK
        }
        ans.push_back(graph[l][remains[a]]);
    }
    assert(int(ans.size()) == n - 1);
    return ans;
}

vec find_roads(int n, vec u, vec v) {
    int m = u.size();
    std::vector<vec> graph(n, vec(n, -1));
    for (int k = 0; k < m; k++)
        graph[u[k]][v[k]] = graph[v[k]][u[k]] = k;
    // TODO
    if (m == n * (n - 1) / 2)
        return complete(n, graph);
    else
        return square(n, m, graph);
}

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