Submission #828222

#	Time	Username	Problem	Language	Result	Execution time	Memory
828222		Minindu206	Simurgh (IOI17_simurgh)	C++14	0 / 100	4 ms	340 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
struct dsu {
    int n;
    vector<int> rank, parent;
    void init(int _n)
    {
        this->n = _n;
        rank.resize(n + 1, 0);
        parent.resize(n + 1, -1);
    }
    int finds(int i)
    {
        if(parent[i] == -1)
            return i;
        return parent[i] = finds(parent[i]);
    }
    void unions(int a, int b)
    {
        int s1 = finds(a);
        int s2 = finds(b);

        if(s1 == s2)
            return;
        if(rank[s1] < rank[s2])
            swap(s1, s2);
        parent[s2] = s1;
        rank[s1] += rank[s2];
    }
};
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	dsu d;
	for(int i=0;i<(1<<m);i++)
	{
		vector<int> arr;
		d.init(n);
		for(int j=0;j<m;j++)
		{
			if(!(i & (1 << j)))
				continue;
			d.unions(u[j], v[j]);
			arr.push_back(j);
		}
		int flag = 1;
		for(int j=1;j<n;j++)
		{
			if(d.finds(j) != d.finds(0))
				flag = 0;
		}
		if((int)arr.size() != n - 1)
			continue;
		if(flag && count_common_roads(arr) == n - 1)
			return arr;
	}
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:34:6: warning: control reaches end of non-void function [-Wreturn-type]
   34 |  dsu d;
      |      ^

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