Submission #42951

#	Time	Username	Problem	Language	Result	Execution time	Memory
42951		MatheusLealV	Simurgh (IOI17_simurgh)	C++14	13 / 100	674 ms	876 KiB

simurgh

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

int n, m;

int ok[N], pai[N];

vector<int> grafo[N];

int Find(int x)
{
    if(x == pai[x]) return x;

    return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
    a = Find(a), b = Find(b);

    if(a == b) return;

    pai[a] = b;
}

bool check(vector<int> vet, vector<int> &u, vector<int> &v)
{
    if(vet.size() != n - 1) return false;

    for(int i = 0; i < n; i++) pai[i] = i;

    for(auto x: vet)
    {
        join(u[x], v[x]);
    }

    set<int> ss;

    for(int i = 0; i < n; i++) ss.insert(Find(i));

    if(ss.size() != 1) return false;

    if(count_common_roads(vet) == n - 1) return true;

    else return false;
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v)
{
    n = n_;

    m = u.size();

    for(int i = 0; i < m; i++) grafo[u[i]].push_back(v[i]), grafo[v[i]].push_back(u[i]);

    for(int mask = 0; mask < (1<<m); mask ++)
    {
        vector<int> aux;

        for(int i = 0; i < m; i++)
        {
            if(mask & (1<<i))
            {
                aux.push_back(i);
            }
        }

        if(check(aux, u, v)) return aux;
    }

    return u;
}

Compilation message (stderr)

simurgh.cpp: In function 'bool check(std::vector<int>, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vet.size() != n - 1) return false;
                   ^

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