제출 #1311850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311850		nikaa123	Simurgh (IOI17_simurgh)	C++20	30 / 100	463 ms	3888 KiB

simurgh

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

using namespace std;

static int status[300005]; 
static vector<pair<int, int>> adj[505];
static int depth[505], parent_node[505], parent_edge[505];
static bool visited[505];
static vector<int> tree_edges;


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) {
    visited[u] = true;
    depth[u] = d;
    for (auto &edge : adj[u]) {
        int v = edge.first, id = edge.second;
        if (v == p) continue;
        if (!visited[v]) {
            parent_node[v] = u;
            parent_edge[v] = id;
            tree_edges.push_back(id);
            dfs(v, u, d + 1);
        }
    }
}


void identify_initial_tree(int n, const vector<int>& u, const vector<int>& v) {
    for (int i = 0; i < u.size(); i++) {
        if (status[i] != -1) continue;
        bool is_in_tree = false;
        for (int te : tree_edges) if (te == i) is_in_tree = true;
        if (is_in_tree) continue;

   
        vector<int> cycle;
        int x = u[i], y = v[i];
        if (depth[x] < depth[y]) swap(x, y);
        while (depth[x] > depth[y]) {
            cycle.push_back(parent_edge[x]);
            x = parent_node[x];
        }
        while (x != y) {
            cycle.push_back(parent_edge[x]);
            cycle.push_back(parent_edge[y]);
            x = parent_node[x]; y = parent_node[y];
        }
        cycle.push_back(i);

        int known_edge = -1;
        for (int ce : cycle) if (status[ce] != -1) known_edge = ce;

        int st = 0;
        if (known_edge != -1) st = status[known_edge];

        vector<int> query_results(cycle.size());
        int max_val = -1, min_val = 1e9;

        for (int j = 0; j < cycle.size(); j++) {
            if (known_edge != -1 && status[cycle[j]] != -1 && cycle[j] != known_edge) {
                query_results[j] = -2; continue;
            }
            vector<int> q;
            for (int te : tree_edges) {
                bool in_cycle = false;
                for (int ce : cycle) if (ce == te) in_cycle = true;
                if (!in_cycle) q.push_back(te);
            }
            for (int k = 0; k < cycle.size(); k++) if (k != j) q.push_back(cycle[k]);
            
            query_results[j] = count_common_roads(q);
            max_val = max(max_val, query_results[j]);
            min_val = min(min_val, query_results[j]);
        }

        for (int j = 0; j < cycle.size(); j++) {
            if (query_results[j] == -2) continue;
            if (max_val == min_val) status[cycle[j]] = st;
            else status[cycle[j]] = (query_results[j] == min_val ? 1 : 0);
        }
    }
    for (int te : tree_edges) if (status[te] == -1) status[te] = 1;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();
    for (int i = 0; i < m; i++) {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
        status[i] = -1;
    }

    dfs(0, -1, 0);
    identify_initial_tree(n, u, v);

 
    for (int i = 0; i < n; i++) {
        vector<int> candidates;
        for (auto &edge : adj[i]) {
            int id = edge.second;
       
            if (i < (u[id] == i ? v[id] : u[id]) && status[id] == -1) {
                candidates.push_back(id);
            }
        }

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

    
            DSU dsu(n);
            vector<int> base_q;
            for (int id : cur_candidates) dsu.unite(u[id], v[id]);
            
            int royal_in_tree = 0;
            for (int te : tree_edges) {
                if (dsu.unite(u[te], v[te])) {
                    base_q.push_back(te);
                    if (status[te] == 1) royal_in_tree++;
                }
            }
            
            vector<int> final_q = base_q;
            for (int id : cur_candidates) final_q.push_back(id);
            
     
            int total_royal = count_common_roads(final_q);
            int royal_in_candidates = total_royal - royal_in_tree;

            if (royal_in_candidates == 0) {
                for (int id : cur_candidates) status[id] = 0;
            } else if (cur_candidates.size() == royal_in_candidates) {
                for (int id : cur_candidates) status[id] = 1;
            } else {
                int mid = cur_candidates.size() / 2;
                vector<int> left(cur_candidates.begin(), cur_candidates.begin() + mid);
                vector<int> right(cur_candidates.begin() + mid, cur_candidates.end());
                self(self, left);
                self(self, right);
            }
        };
        solve(solve, candidates);
    }

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

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