Submission #425183

#	Time	Username	Problem	Language	Result	Execution time	Memory
425183		timmyfeng	Simurgh (IOI17_simurgh)	C++17	100 / 100	340 ms	6596 KiB

simurgh

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

#include "simurgh.h"

const int N = 500;

int par[N], edge[N], depth[N], deg[N], matches[N], dsu[N], n;
bool royal[N], visited[N], observed[N];
vector<int> span, ans, not_ans, u, v;
vector<array<int, 2>> adj[N];

void dfs(int u) {
    visited[u] = true;
    for (auto [c, e] : adj[u]) {
        if (!visited[c]) {
            span.push_back(e);
            depth[c] = depth[u] + 1;
            edge[c] = e;
            par[c] = u;
            dfs(c);
        }
    }
}

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

bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) {
        if (-dsu[u] > -dsu[v]) {
            swap(u, v);
        }
        dsu[v] += dsu[u];
        dsu[u] = v;
        return true;
    }
    return false;
}

int get(vector<int> &tree) {
    fill(dsu, dsu + n, -1);

    for (auto i : tree) {
        unite(u[i], v[i]);
    }

    for (auto i : not_ans) {
        if (unite(u[i], v[i])) {
            tree.push_back(i);
        }
    }

    int offset = 0;
    for (auto i : ans) {
        if (unite(u[i], v[i])) {
            tree.push_back(i);
            ++offset;
        }
    }

    return offset;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size(); ::n = n, ::u = u, ::v = v;

    for (int i = 0; i < m; ++i) {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }

    dfs(0);

    int init = count_common_roads(span);
    for (int i = 0; i < m; ++i) {
        if (depth[u[i]] > depth[v[i]]) {
            swap(u[i], v[i]);
        }

        if (depth[u[i]] + 1 == depth[v[i]]) {
            continue;
        }

        bool learn = false;
        for (int j = v[i]; j != u[i]; j = par[j]) {
            learn |= !observed[j];
        }

        if (!learn) {
            continue;
        }

        int reference = -1, mini = n - 1, maxi = 0;
        for (int j = v[i]; j != u[i]; j = par[j]) {
            vector<int> cycle = span;
            cycle.erase(find(cycle.begin(), cycle.end(), edge[j]));
            cycle.push_back(i);

            int value = -1;
            if (!observed[j]) {
                value = matches[j] = count_common_roads(cycle);
            } else if (reference == -1) {
                value = count_common_roads(cycle);
                reference = j;
            }

            if (value != -1) {
                mini = min(mini, value);
                maxi = max(maxi, value);
            }
        }

        for (int j = v[i]; j != u[i]; j = par[j]) {
            if (!observed[j]) {
                observed[j] = true;
                if (mini == maxi) {
                    if (reference == -1) {
                        royal[j] = mini < init;
                    } else {
                        royal[j] = royal[reference];
                    }
                } else {
                    royal[j] = matches[j] == mini;
                }
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        (royal[i] || !observed[i] ? ans : not_ans).push_back(edge[i]);
    }

    vector<int> stk;
    for (int i = 0; i < n; ++i) {
        vector<int> star;
        for (auto [j, e] : adj[i]) {
            if (count(ans.begin(), ans.end(), e) == 0) {
                star.push_back(e);
            }
        }
        int offset = get(star);

        deg[i] = count_common_roads(star) - offset;
        if (deg[i] == 1) {
            stk.push_back(i);
        }
    }

    while (!stk.empty()) {
        int i = stk.back();
        stk.pop_back();
        if (deg[i] == 0) {
            continue;
        }

        vector<int> candidates;
        for (auto [j, e] : adj[i]) {
            if (count(ans.begin(), ans.end(), e) == 0) {
                candidates.push_back(e);
            }
        }

        int low = 0, high = candidates.size() - 1;
        while (low < high) {
            int mid = (low + high) / 2;

            vector<int> star = vector<int>(candidates.begin(), candidates.begin() + mid + 1);
            int offset = get(star);

            if (count_common_roads(star) - offset > 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        int e = candidates[low], j = i ^ u[e] ^ v[e];
        ans.push_back(e);
        if (--deg[j] == 1) {
            stk.push_back(j);
        }
    }

    return ans;
}

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