Submission #619731

#	Time	Username	Problem	Language	Result	Execution time	Memory
619731		Sergio_2357	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	340 KiB

simurgh

#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, -1);
        sz = vi(n, 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)) {
            //cout << "HERE" << endl;
            return lst;
        } else {
            //cout << "Not here" << endl;
        }
    }
    //cout << "Not found" << endl;
    return to_list((1ll << n - 1) - 1);
}

Compilation message (stderr)

simurgh.cpp: In function 'bool test(vi, vi)':
simurgh.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < u.size(); i++)
      |                     ~~^~~~~~~~~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:69:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(lst) == n - 1)) {
      |             ~~~~~~~~~~^~~~~~~~
simurgh.cpp:77:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   77 |     return to_list((1ll << n - 1) - 1);
      |                            ~~^~~

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