oj.uz

답안 #114722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114722 2019-06-02T12:43:05 Z faustaadp Simurgh (IOI17_simurgh) C++17
0 / 100
 2 ms 384 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,p[550],i;
ll X[125050];
ll Y[125050];
ll z[125050];
vector<int> r;
vector<pair<ll,ll> > isi;
ll car(ll aa)
{
	if(p[aa]==aa)
		return aa;
	else
		return p[aa]=car(p[aa]);
}
void cek(ll aa)
{
	vector<int> tan;
	ll ii;
	for(ii=0;ii<n;ii++)p[ii]=ii;
	for(ii=0;ii<r.size();ii++)
		if(ii!=aa)
		{
			p[car(X[r[ii]])]=car(Y[r[ii]]);
			tan.pb(ii);
		}
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
		//	cout<<aa<<" "<<ii<<"\n";
			tan.pb(ii);
			isi.pb(mp(-count_common_roads(tan),ii));
			tan.pop_back();
		}
	sort(isi.begin(),isi.end());
	z[isi[0].se]=1;
//	r[aa]=isi[0].se;
}
std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) 
{
	n=N;
	m=U.size();
	for(i=0;i<m;i++)
		X[i]=U[i];
	for(i=0;i<m;i++)
		Y[i]=V[i];
	for(i=0;i<n;i++)p[i]=i;
	for(i=0;i<m;i++)
		if(car(U[i])!=car(V[i]))
		{
			p[car(U[i])]=car(V[i]);
			r.pb(i);
		}
	//cout<<count_common_roads(r)<<"\n";
	for(i=0;i<r.size();i++)
	{
		isi.clear();
		cek(i);
	//	cout<<i<<" "<<r[i]<<"\n";
	}
	r.clear();
	for(i=0;i<m;i++)
		if(z[i])
			r.pb(i);
//	if(count_common_roads(r)!=n-1)
//		while(1);
	//for(i=0;i<r.size();i++)
	return r;
}

Compilation message

simurgh.cpp: In function 'void cek(ll)':
simurgh.cpp:27:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<r.size();ii++)
           ~~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:61:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++)
          ~^~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

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