oj.uz

Submission #708622

# Submission time Handle Problem Language Result Execution time Memory
708622 2023-03-12T04:53:05 Z jophyyjh Simurgh (IOI17_simurgh) C++14
51 / 100
 226 ms 3096 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();
        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 ask1 = ans;
            int half = (b - a + 1) / 2;
            for (int k = a; k < a + half; k++)
                ask1.push_back(graph[remains[k]][remains[k + half]]);
            if (a % 2 == b % 2)
                ask1.push_back(graph[remains.front()][remains.back()]);
            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;
            else
                a = b;
        }
        int neighb = remains[a];
        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 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 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 292 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 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 292 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct
14 Correct 3 ms 300 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 3 ms 212 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 2 ms 212 KB correct
20 Correct 2 ms 212 KB correct
21 Correct 3 ms 212 KB correct
22 Correct 2 ms 340 KB correct
23 Correct 2 ms 212 KB correct
24 Correct 2 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 3 ms 300 KB correct
27 Correct 2 ms 212 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 3 ms 300 KB correct
31 Correct 2 ms 212 KB correct
32 Correct 2 ms 212 KB correct
33 Correct 3 ms 212 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 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 292 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct
14 Correct 3 ms 300 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 3 ms 212 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 2 ms 212 KB correct
20 Correct 2 ms 212 KB correct
21 Correct 3 ms 212 KB correct
22 Correct 2 ms 340 KB correct
23 Correct 2 ms 212 KB correct
24 Correct 2 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 3 ms 300 KB correct
27 Correct 2 ms 212 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 3 ms 300 KB correct
31 Correct 2 ms 212 KB correct
32 Correct 2 ms 212 KB correct
33 Correct 3 ms 212 KB correct
34 Correct 201 ms 1280 KB correct
35 Correct 217 ms 1260 KB correct
36 Correct 196 ms 1028 KB correct
37 Correct 31 ms 468 KB correct
38 Correct 226 ms 1236 KB correct
39 Correct 215 ms 1172 KB correct
40 Correct 190 ms 948 KB correct
41 Correct 217 ms 1280 KB correct
42 Correct 215 ms 1284 KB correct
43 Correct 137 ms 1032 KB correct
44 Correct 122 ms 852 KB correct
45 Correct 142 ms 816 KB correct
46 Correct 109 ms 724 KB correct
47 Correct 64 ms 644 KB correct
48 Correct 24 ms 548 KB correct
49 Correct 32 ms 468 KB correct
50 Correct 71 ms 596 KB correct
51 Correct 140 ms 896 KB correct
52 Correct 122 ms 852 KB correct
53 Correct 108 ms 812 KB correct
54 Correct 143 ms 928 KB correct
55 Correct 138 ms 824 KB correct
56 Correct 147 ms 904 KB correct
57 Correct 148 ms 852 KB correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 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 292 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 300 KB correct
14 Correct 3 ms 300 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 3 ms 212 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 2 ms 212 KB correct
20 Correct 2 ms 212 KB correct
21 Correct 3 ms 212 KB correct
22 Correct 2 ms 340 KB correct
23 Correct 2 ms 212 KB correct
24 Correct 2 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 3 ms 300 KB correct
27 Correct 2 ms 212 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 3 ms 300 KB correct
31 Correct 2 ms 212 KB correct
32 Correct 2 ms 212 KB correct
33 Correct 3 ms 212 KB correct
34 Correct 201 ms 1280 KB correct
35 Correct 217 ms 1260 KB correct
36 Correct 196 ms 1028 KB correct
37 Correct 31 ms 468 KB correct
38 Correct 226 ms 1236 KB correct
39 Correct 215 ms 1172 KB correct
40 Correct 190 ms 948 KB correct
41 Correct 217 ms 1280 KB correct
42 Correct 215 ms 1284 KB correct
43 Correct 137 ms 1032 KB correct
44 Correct 122 ms 852 KB correct
45 Correct 142 ms 816 KB correct
46 Correct 109 ms 724 KB correct
47 Correct 64 ms 644 KB correct
48 Correct 24 ms 548 KB correct
49 Correct 32 ms 468 KB correct
50 Correct 71 ms 596 KB correct
51 Correct 140 ms 896 KB correct
52 Correct 122 ms 852 KB correct
53 Correct 108 ms 812 KB correct
54 Correct 143 ms 928 KB correct
55 Correct 138 ms 824 KB correct
56 Correct 147 ms 904 KB correct
57 Correct 148 ms 852 KB correct
58 Correct 1 ms 212 KB correct
59 Correct 0 ms 212 KB correct
60 Incorrect 150 ms 3096 KB WA in grader: NO
61 Halted 0 ms 0 KB -