oj.uz

Submission #49161

# Submission time Handle Problem Language Result Execution time Memory
49161 2018-05-22T22:25:17 Z StainFizzy Simurgh (IOI17_simurgh) C++14
13 / 100
 1052 ms 748 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define N 10
using namespace std;

int parent[N], Rank[N], mm, nn;

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

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

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

	if(a == b) return;

	if(Rank[a] > Rank[b]) parent[b] = a;

	else if(Rank[a] < Rank[b]) parent[a] = b;

	else parent[a] = b, Rank[b] ++;
}

std::vector<int> find_roads(int n_, std::vector<int> u, std::vector<int> v)
{
	mm = u.size(), nn = n_;

	for(int mask = 0; mask < (1<<mm); mask ++)
	{
		vector<int> roads;

		for(int i = 0; i < mm; i++) if(mask & (1<<i)) roads.push_back(i);

		for(int i = 0; i < nn; i++) parent[i] = i, Rank[i] = 0;

		set<int> spower;

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

		for(int i = 0; i < nn; i++) spower.insert(Find(i));

		if(spower.size() == 1 && roads.size() == nn - 1)
		{
			int q =  count_common_roads(roads);

			if(q == nn - 1)
			{
				return roads;
			}
		}
	}	
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:49:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(spower.size() == 1 && roads.size() == nn - 1)
                            ~~~~~~~~~~~~~^~~~~~~~~
simurgh.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 504 KB correct
2 Correct 855 ms 524 KB correct
3 Correct 1052 ms 524 KB correct
4 Correct 6 ms 536 KB correct
5 Correct 3 ms 536 KB correct
6 Correct 24 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 7 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 11 ms 696 KB correct
13 Correct 291 ms 732 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 504 KB correct
2 Correct 855 ms 524 KB correct
3 Correct 1052 ms 524 KB correct
4 Correct 6 ms 536 KB correct
5 Correct 3 ms 536 KB correct
6 Correct 24 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 7 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 11 ms 696 KB correct
13 Correct 291 ms 732 KB correct
14 Incorrect 7 ms 748 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 504 KB correct
2 Correct 855 ms 524 KB correct
3 Correct 1052 ms 524 KB correct
4 Correct 6 ms 536 KB correct
5 Correct 3 ms 536 KB correct
6 Correct 24 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 7 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 11 ms 696 KB correct
13 Correct 291 ms 732 KB correct
14 Incorrect 7 ms 748 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB correct
2 Incorrect 10 ms 748 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 504 KB correct
2 Correct 855 ms 524 KB correct
3 Correct 1052 ms 524 KB correct
4 Correct 6 ms 536 KB correct
5 Correct 3 ms 536 KB correct
6 Correct 24 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 7 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 11 ms 696 KB correct
13 Correct 291 ms 732 KB correct
14 Incorrect 7 ms 748 KB WA in grader: NO
15 Halted 0 ms 0 KB -