| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1311854 | nikaa123 | Simurgh (IOI17_simurgh) | C++20 | 0 ms | 0 KiB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
// Using fixed sizes based on constraints
static int edge_status[300005];
static vector<pair<int, int>> graph_adj[505];
static int dpt[505], par_n[505], par_e[505];
static bool vis[505];
static vector<int> t_edges;
struct DSU_Structure {
vector<int> p;
DSU_Structure(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 run_dfs(int u, int p, int d) {
vis[u] = true;
dpt[u] = d;
for (auto &edge : graph_adj[u]) {
int v = edge.first, id = edge.second;
if (v == p) continue;
if (!vis[v]) {
par_node[v] = u;
par_edge[v] = id;
t_edges.push_back(id);
run_dfs(v, u, d + 1);
}
}
}
static bool is_tree_edge[300005];
void identify_tree_edges(int n, const vector<int>& u, const vector<int>& v) {
for (int i = 0; i < u.size(); i++) {
if (is_tree_edge[i] || edge_status[i] != -1) continue;
vector<int> cycle_indices;
int x = u[i], y = v[i];
while (x != y) {
if (dpt[x] > dpt[y]) {
cycle_indices.push_back(par_edge[x]);
x = par_node[x];
} else {
cycle_indices.push_back(par_edge[y]);
y = par_node[y];
}
}
cycle_indices.push_back(i);
int ref_edge = -1;
for (int e_id : cycle_indices) {
if (edge_status[e_id] != -1) {
ref_edge = e_id;
break;
}
}
vector<int> query_results(cycle_indices.size(), -1);
int mx = -1, mn = 1e9;
for (int j = 0; j < cycle_indices.size(); j++) {
int current_e = cycle_indices[j];
if (ref_edge != -1 && edge_status[current_e] != -1 && current_e != ref_edge) continue;
vector<int> q;
for (int te : t_edges) {
bool in_cycle = false;
for (int ce : cycle_indices) if (ce == te) in_cycle = true;
if (!in_cycle) q.push_back(te);
}
for (int k = 0; k < cycle_indices.size(); k++) {
if (k != j && is_tree_edge[cycle_indices[k]]) q.push_back(cycle_indices[k]);
}
if (j != (int)cycle_indices.size() - 1) q.push_back(i);
query_results[j] = count_common_roads(q);
mx = max(mx, query_results[j]);
mn = min(mn, query_results[j]);
}
for (int j = 0; j < cycle_indices.size(); j++) {
if (query_results[j] == -1) continue;
if (mx == mn) edge_status[cycle_indices[j]] = (ref_edge != -1 ? edge_status[ref_edge] : 0);
else edge_status[cycle_indices[j]] = (query_results[j] == mn ? 1 : 0);
}
}
for (int te : t_edges) if (edge_status[te] == -1) edge_status[te] = 1;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
t_edges.clear();
for (int i = 0; i < n; i++) {
graph_adj[i].clear();
vis[i] = false;
}
for (int i = 0; i < m; i++) {
graph_adj[u[i]].push_back({v[i], i});
graph_adj[v[i]].push_back({u[i], i});
edge_status[i] = -1;
is_tree_edge[i] = false;
}
run_dfs(0, -1, 0);
for (int te : t_edges) is_tree_edge[te] = true;
identify_tree_edges(n, u, v);
for (int i = 0; i < n; i++) {
vector<int> unknowns;
for (auto &e : graph_adj[i]) {
int id = e.second;
int other = (u[id] == i ? v[id] : u[id]);
if (i < other && edge_status[id] == -1) unknowns.push_back(id);
}
auto binary_solve = [&](auto self, vector<int> cand) -> void {
if (cand.empty()) return;
DSU_Structure dsu(n);
for (int id : cand) dsu.unite(u[id], v[id]);
vector<int> q = cand;
int tree_score = 0;
for (int te : t_edges) {
if (dsu.unite(u[te], v[te])) {
q.push_back(te);
if (edge_status[te] == 1) tree_score++;
}
}
int total = count_common_roads(q);
int found = total - tree_score;
if (found == 0) {
for (int id : cand) edge_status[id] = 0;
} else if (found == (int)cand.size()) {
for (int id : cand) edge_status[id] = 1;
} else {
int mid = cand.size() / 2;
self(self, vector<int>(cand.begin(), cand.begin() + mid));
self(self, vector<int>(cand.begin() + mid, cand.end()));
}
};
binary_solve(binary_solve, unknowns);
}
vector<int> final_set;
for (int i = 0; i < m; i++) if (edge_status[i] == 1) final_set.push_back(i);
return final_set;
}