oj.uz

답안 #828233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828233 2023-08-17T06:55:41 Z Minindu206 Simurgh (IOI17_simurgh) C++14
0 / 100
 4 ms 292 KB 
#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);

		int flag = 1;
		for(int j=0;j<m;j++)
		{
			if(!(i & (1 << j)))
				continue;
			if(d.finds(u[j]) == d.finds(v[j]))
				flag = 0;
			d.unions(u[j], v[j]);
			arr.push_back(j);
		}
		for(int j=0;j<n;j++)
		{
			if(d.finds(j) != d.finds(0))
				flag = 0;
		}
		if(!flag)
          	continue;
		if(count_common_roads(arr) == n - 1)
			return arr;
	}
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB correct
2 Runtime error 4 ms 292 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -