# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1083303 | Math4Life2020 | Simurgh (IOI17_simurgh) | C++17 | 1250 ms | 1048576 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#include "simurgh.h"
using ll = long long; using pii = pair<ll,ll>;
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]) {
a=f[a];
}
while (b != f[b]) {
b=f[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;
}
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |