Submission #1311863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311863		nikaa123	Simurgh (IOI17_simurgh)	C++20	0 / 100	1963 ms	1114112 KiB

simurgh

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

using namespace std;

// Global state variables
static int edge_status[30005]; 
static vector<pair<int, int>> adj[505];
static int dpt[505], par_n[505], par_e[505];
static bool vis[505];
static vector<int> tree_edges;
static bool is_tree_edge[30005];

struct DSU {
    vector<int> p;
    DSU(int n) { p.resize(n); iota(p.begin(), p.end(), 0); }
    int find(int i) { return (p[i] == i) ? i : (p[i] = find(p[i])); }
    bool unite(int i, int j) {
        int root_i = find(i), root_j = find(j);
        if (root_i != root_j) { p[root_i] = root_j; return true; }
        return false;
    }
};

void dfs(int u, int p, int d) {
    vis[u] = true;
    dpt[u] = d;
    for (auto &edge : adj[u]) {
        int v = edge.first, id = edge.second;
        if (v == p) continue;
        if (!vis[v]) {
            par_n[v] = u;
            par_e[v] = id;
            tree_edges.push_back(id);
            is_tree_edge[id] = true;
            dfs(v, u, d + 1);
        }
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();
    
    // 1. Reset all structures
    tree_edges.clear();
    for (int i = 0; i < n; i++) {
        adj[i].clear();
        vis[i] = false;
    }
    for (int i = 0; i < m; i++) {
        edge_status[i] = -1;
        is_tree_edge[i] = false;
    }

    // 2. Build initial DFS Tree
    dfs(0, -1, 0);

    // 3. Phase 1: Use cycles to classify tree edges
    for (int i = 0; i < m; i++) {
        if (is_tree_edge[i] || edge_status[i] != -1) continue;

        vector<int> cycle;
        int x = u[i], y = v[i];
        while (x != y) {
            if (dpt[x] > dpt[y]) { cycle.push_back(par_e[x]); x = par_n[x]; }
            else { cycle.push_back(par_e[y]); y = par_n[y]; }
        }
        cycle.push_back(i); // back-edge is the last element

        int ref_edge = -1;
        for (int e : cycle) {
            if (edge_status[e] != -1) {
                ref_edge = e;
                break;
            }
        }

        vector<int> res(cycle.size(), -1);
        int mx = -1, mn = 1e9;

        for (int j = 0; j < (int)cycle.size(); j++) {
            int cur = cycle[j];
            // If we already know the status, we only query the reference edge
            if (ref_edge != -1 && edge_status[cur] != -1 && cur != ref_edge) continue;

            vector<int> q;
            // Build a spanning tree by removing cycle[j] and ensuring i (back-edge) connects it
            for (int te : tree_edges) {
                bool in_c = false;
                for (int ce : cycle) if (ce == te) in_c = true;
                if (!in_c) q.push_back(te);
            }
            for (int k = 0; k < (int)cycle.size() - 1; k++) {
                if (k != j) q.push_back(cycle[k]);
            }
            if (j != (int)cycle.size() - 1) q.push_back(i);

            res[j] = count_common_roads(q);
            mx = max(mx, res[j]);
            mn = min(mn, res[j]);
        }

        for (int j = 0; j < (int)cycle.size(); j++) {
            if (res[j] == -1) continue;
            if (mx == mn) {
                // If all results are the same, they share status with reference (or are 0)
                edge_status[cycle[j]] = (ref_edge != -1 ? edge_status[ref_edge] : 0);
            } else {
                // The edge whose removal yields the minimum result is the Royal Road (1)
                edge_status[cycle[j]] = (res[j] == mn ? 1 : 0);
            }
        }
    }
    
    // Tree edges not part of any cycle are bridges (always royal)
    for (int te : tree_edges) if (edge_status[te] == -1) edge_status[te] = 1;

    // 4. Phase 2: Binary search for remaining non-tree edges
    for (int i = 0; i < n; i++) {
        vector<int> candidates;
        for (auto &edge : adj[i]) {
            int id = edge.second;
            int other = (u[id] == i ? v[id] : u[id]);
            if (i < other && edge_status[id] == -1) candidates.push_back(id);
        }

        auto solve = [&](auto self, vector<int> c) -> void {
            if (c.empty()) return;

            DSU dsu(n);
            vector<int> q;
            // Add candidates but prevent internal cycles
            for (int id : c) if (dsu.unite(u[id], v[id])) q.push_back(id);
            
            int tree_royals_count = 0;
            for (int te : tree_edges) {
                if (dsu.unite(u[te], v[te])) {
                    q.push_back(te);
                    if (edge_status[te] == 1) tree_royals_count++;
                }
            }
            
            int found_in_set = count_common_roads(q) - tree_royals_count;

            if (found_in_set == 0) {
                for (int id : c) edge_status[id] = 0;
            } else if (found_in_set == (int)c.size()) {
                for (int id : c) edge_status[id] = 1;
            } else {
                int mid = c.size() / 2;
                self(self, vector<int>(c.begin(), c.begin() + mid));
                self(self, vector<int>(c.begin() + mid, c.end()));
            }
        };
        solve(solve, candidates);
    }

    vector<int> result;
    for (int i = 0; i < m; i++) if (edge_status[i] == 1) result.push_back(i);
    return result;
}

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