# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
619736 | Sergio_2357 | Simurgh (IOI17_simurgh) | C++17 | 1 ms | 212 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.
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
struct DSU {
vi v, sz;
int cg;
int find(int x)
{
if (v[x] == -1)
return x;
v[x] = find(v[x]);
return v[x];
}
void join(int a, int b)
{
a = find(a);
b = find(b);
if (a == b)
return;
cg--;
if (sz[a] > sz[b])
swap(a, b);
v[a] = b;
sz[b] += sz[a];
}
DSU(int n)
{
v = vi(n+10, -1);
sz = vi(n+10, 1);
cg = n;
}
};
bool test(vi u, vi v)
{
DSU dsu(u.size());
for (int i = 0; i < u.size(); i++)
dsu.join(u[i], v[i]);
return dsu.cg == 1;
}
vi to_list(int b)
{
vi r;
for (int i = 0; i < 25; i++) {
if (b & (1ll << i))
r.push_back(i);
}
return r;
}
vi find_roads(int n, vi u, vi v)
{
//cout << "HELLO" << endl;
for (int b = 0; b < (1ll << (u.size())); b++) {
vi tu, tv;
vi lst = to_list(b);
for (int x : lst) {
tu.push_back(u[x]);
tv.push_back(v[x]);
}
//for (int x : to_list(b))
// cout << x << ' ';
//cout << endl;
if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(lst) == n - 1))
return lst;
}
//cout << "Not found" << endl;
return to_list((1ll << n - 1) - 1);
}
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... |