oj.uz

Submission #708644

# Submission time Handle Problem Language Result Execution time Memory
708644 2023-03-12T06:16:15 Z jophyyjh Simurgh (IOI17_simurgh) C++14
13 / 100
 2 ms 340 KB 
/**
 * [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, 2n * 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;     // Results from count_common_roads()
        // after this loop, is_ans[original] must be correct
        for (int neighb = 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.push_back(switched_num);
            if (switched_num > base_num)
                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] == 1)
            leaves.push(k);
    }
    vec ans;
    std::vector<bool> active(n, true);
    while (!leaves.empty() && int(ans.size()) < n - 1) {
        int l = leaves.front();
        std::cerr << "[debug] processing leaf " << l << std::endl;
        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) {
            int half = (b - a + 1) / 2;
            vec ask1;
            std::vector<bool> appeared(n, false);
            for (int k = a; k < a + half; k++) {
                ask1.push_back(graph[remains[k]][remains[k + half]]);
                appeared[remains[k]] = appeared[remains[k + half]] = true;
            }
            for (int k = 0; k < n; k++) {
                if (k != l && !appeared[k])
                    ask1.push_back(graph[remains[a]][k]);
            }
            vec ask2 = ask1;
            for (int k = a; k < a + half; k++) {
                ask1.push_back(graph[remains[k]][l]);
                ask2.push_back(graph[remains[k + half]][l]);
            }
            int r1 = count_common_roads(ask1), r2 = count_common_roads(ask2);
            if (r1 > r2)
                b = a + half - 1;
            else if (r1 < r2)
                a = a + half, b -= (a % 2 == b % 2 ? 1 : 0);
            else
                a = b;
        }
        int neighb = remains[a];
        std::cerr << "[debug] found neighb " << neighb << std::endl;
        ans.push_back(graph[l][neighb]);
        deg[neighb]--;
        if (deg[neighb] == 1)
            leaves.push(neighb);
    }
    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;
    if (m == n * (n - 1) / 2)
        return complete(n, graph);
    else
        return square(n, m, graph);
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct
14 Incorrect 2 ms 340 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct
14 Incorrect 2 ms 340 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct
14 Incorrect 2 ms 340 KB WA in grader: NO
15 Halted 0 ms 0 KB -