| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1311851 | nikaa123 | Simurgh (IOI17_simurgh) | C++20 | 0 ms | 0 KiB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
static int edge_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);
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < m; i++) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
edge_status[i] = -1;
visited[i] = false;
}
dfs(0, -1, 0);
for (int i = 0; i < m; i++) {
bool is_tree = false;
for (int te : tree_edges) if (te == i) is_tree = true;
if (is_tree || edge_status[i] != -1) continue;
vector<int> cycle = {i};
int x = u[i], y = v[i];
while (x != y) {
if (depth[x] > depth[y]) { cycle.push_back(parent_edge[x]); x = parent_node[x]; }
else { cycle.push_back(parent_edge[y]); y = parent_node[y]; }
}
int known_idx = -1;
for (int e : cycle) if (edge_status[e] != -1) known_idx = e;
int st = 0;
if (known_idx != -1) st = status[known_idx];
vector<int> results(cycle.size(), -1);
int max_v = -1, min_v = 2e9;
for (int j = 0; j < cycle.size(); j++) {
if (known_idx != -1 && edge_status[cycle[j]] != -1 && cycle[j] != known_idx) continue;
vector<int> q;
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 < cycle.size(); k++) if (j != k) q.push_back(cycle[k]);
results[j] = count_common_roads(q);
max_v = max(max_v, results[j]);
min_v = min(min_v, results[j]);
}
for (int j = 0; j < cycle.size(); j++) {
if (results[j] == -1) continue;
if (max_v == min_v) edge_status[cycle[j]] = st;
else edge_status[cycle[j]] = (results[j] == min_v ? 1 : 0);
}
}
for (int te : tree_edges) if (edge_status[te] == -1) edge_status[te] = 1;
vector<int> non_tree;
for (int i = 0; i < m; i++) {
bool is_tree = false;
for (int te : tree_edges) if (te == i) is_tree = true;
if (!is_tree) non_tree.push_back(i);
}
auto count_royals_in_subset = [&](const vector<int>& subset) {
if (subset.empty()) return 0;
DSU dsu(n);
vector<int> q = subset;
for (int id : subset) dsu.unite(u[id], v[id]);
int tree_royals = 0;
for (int te : tree_edges) {
if (dsu.unite(u[te], v[te])) {
q.push_back(te);
if (edge_status[te] == 1) tree_royals++;
}
}
return count_common_roads(q) - tree_royals;
};
auto find_all = [&](auto self, vector<int> candidates) -> void {
int cnt = count_royals_in_subset(candidates);
if (cnt == 0) return;
if (cnt == candidates.size()) {
for (int id : candidates) edge_status[id] = 1;
return;
}
int mid = candidates.size() / 2;
vector<int> L(candidates.begin(), candidates.begin() + mid);
vector<int> R(candidates.begin() + mid, candidates.end());
self(self, L); self(self, R);
};
for (int i = 0; i < n; i++) {
vector<int> cur_candidates;
for (auto &e : adj[i]) {
int id = e.second;
if (edge_status[id] == -1 && i < (u[id] == i ? v[id] : u[id])) {
cur_candidates.push_back(id);
}
}
if (!cur_candidates.empty()) find_all(find_all, cur_candidates);
}
vector<int> final_roads;
for (int i = 0; i < m; i++) if (edge_status[i] == 1) final_roads.push_back(i);
return final_roads;
}