# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1083298 | Math4Life2020 | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#include <cinttypes>
#include <cstdio>
using namespace std;
#include "simurgh"
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
ll M = u.size();
vector<vector<int>> combs = {{-1}};
for (ll i=0;i<(N-1);i++) {
vector<vector<int>> combs2;
for (vector<int> v1: combs) {
for (ll e=(v1[v1.size()-1]+1);e<M;e++) {
vector<int> v2 = v1; v2.push_back(e);
combs2.push_back(v2);
}
}
combs = combs2;
}
for (vector<int> v1: combs) {
vector<int> v;
for (ll i=1;i<N;i++) {
v.push_back(v1[i]);
}
ll f[N];
for (ll i=0;i<N;i++) {
f[i]=i;
}
bool valid = 1;
for (ll x: v) {
ll a = u[x]; ll b=v[x];
while (a != f[a]) {
f[a]=a;
}
while (b != f[b]) {
f[b]=b;
}
if (a==b) {
valid = 0; break;
} else {
f[a]=b;
}
}
if (valid) {
ll a0 = count_common_roads(v);
if (a0 == (N-1)) {
return v;
}
}
}
}