| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1160761 | duckindog | Simurgh (IOI17_simurgh) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include "simurgh.h"
#endif
#ifdef LOCAL
static int MAXQ = 30000;
static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;
static void wrong_answer() {
printf("NO\n");
exit(0);
}
static bool is_valid(const vector<int>& r) {
if(int(r.size()) != n - 1)
return false;
for(int i = 0; i < n - 1; i++)
if (r[i] < 0 || r[i] >= m)
return false;
return true;
}
static int _count_common_roads_internal(const vector<int>& r) {
if(!is_valid(r))
wrong_answer();
int common = 0;
for(int i = 0; i < n - 1; i++) {
bool is_common = goal[r[i]];
if (is_common)
common++;
}
return common;
}
int count_common_roads(const vector<int>& r) {
q++;
if(q > MAXQ)
wrong_answer();
return _count_common_roads_internal(r);
}
#endif
const int N = 500 + 10;
vector<pair<int, int>> edges;
vector<pair<int, int>> ad[N];
struct DSU {
int id[N * N];
DSU() { memset(id, -1, sizeof id); }
void clear() { memset(id, -1, sizeof id); }
int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
void add(int u, int v) {
u = root(u); v = root(v);
if (id[u] > id[v]) swap(u, v);
if (u == v) return;
id[u] += id[v];
id[v] = u;
}
bool isCon(int u, int v) { return root(u) == root(v); }
} A, B;
vector<int> paths;
bool findPath(int u, int p, int t) {
if (u == t) return true;
bool ret = false;
for (const auto& [v, idx] : ad[u]) {
if (v == p) continue;
if (findPath(v, u, t)) {
ret = true;
paths.push_back(idx);
}
}
return ret;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
for (int i = 0; i < n - 1; ++i) {
edges.push_back({u[i], v[i]});
}
const int NO = m, YES = m + 1;
vector<int> curList;
for (int i = 0; i < m; ++i) {
if (B.isCon(u[i], v[i])) continue;
B.add(u[i], v[i]);
ad[u[i]].push_back({v[i], i});
ad[v[i]].push_back({u[i], i});
curList.push_back(i);
}
int cnt = count_common_roads(curList);
{ // greedy shit
if (!cnt) {
for (const auto& idx : curList) A.add(idx, NO);
}
if (cnt == n - 1) return curList;
}
// return vector<int>{0, 1, 5};
for (int i = 0; i < m; ++i) {
if (A.isCon(i, NO) || A.isCon(i, YES)) continue;
if (count(curList.begin(), curList.end(), i)) continue;
paths.clear();
for (int j = 0; j < n; ++j) ad[j].clear();
for (const auto& idx : curList) {
ad[u[idx]].push_back({v[idx], idx});
ad[v[idx]].push_back({u[idx], idx});
// cerr << u[idx] << " " << v[idx] << "\n";
}
findPath(u[i], -1, v[i]);
for (const auto& idx : paths) {
if (A.isCon(i, idx)) continue;
vector<int> nList = curList;
nList.erase(find(nList.begin(), nList.end(), idx));
nList.push_back(i);
int nCnt = count_common_roads(nList);
if (nCnt < cnt) { A.add(i, NO); break; }
if (nCnt == cnt) A.add(i, idx);
if (nCnt > cnt) A.add(i, YES), A.add(idx, NO);
}
if (A.isCon(i, YES)) {
B.clear();
curList.clear();
for (int j = 0; j < m; ++j) {
if (A.isCon(j, YES)) {
curList.push_back(j);
B.add(u[j], v[j]);
}
}
for (int j = 0; j < m; ++j) {
if (!B.isCon(u[j], v[j])) {
curList.push_back(j);
B.add(u[j], v[j]);
}
}
cnt = count_common_roads(curList);
}
if (cnt == n - 1) return curList;
}
assert(false);
}
#ifdef LOCAL
int main() {
assert(2 == scanf("%d %d", &n, &m));
u.resize(m);
v.resize(m);
for(int i = 0; i < m; i++)
assert(2 == scanf("%d %d", &u[i], &v[i]));
goal.resize(m, false);
for(int i = 0; i < n - 1; i++) {
int id;
assert(1 == scanf("%d", &id));
goal[id] = true;
}
vector<int> res = find_roads(n, u, v);
if(_count_common_roads_internal(res) != n - 1)
wrong_answer();
printf("YES\n");
return 0;
}
#endif