Submission #584482

#	Time	Username	Problem	Language	Result	Execution time	Memory
584482		PiejanVDC	Simurgh (IOI17_simurgh)	C++17	13 / 100	3086 ms	304 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;

int count_common_roads(const vector<int>& r);


vector<int>par;

int UF(int u) {
    if(par[u] == u)
        return u;
    return par[u] = UF(par[u]);
}

vector<int> find_roads(int n, vector<int>u, vector<int>v) {
    int m = u.size();

    par.resize(n);

    auto P = [&] () {
        for(int i = 0 ; i < n ; i++)
            par[i] = i;
    };

    auto splay = [&] (int a) {
        vector<int>ret;
        for(int i = 0 ; i < m ; i++) {
            if(a & (1 << i))
                ret.push_back(i);
        }
        return ret;
    };

    auto tree = [&] (vector<int>a) {
        P();
        if((int)a.size() != n-1)
            return 0;
        for(auto z : a) {
            int A = UF(u[z]), B = UF(v[z]);
            if(A == B)
                return 0;
            par[A] = B;
        }
        return 1;
    };

    for(int mask = 0 ; mask < (1 << m) ; mask++) {
        if(tree(splay(mask))) {
            vector<int>ask = splay(mask);
            int x = count_common_roads(ask);
            if(x == n-1) {
                return ask;
            }
        }
    }
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30