답안 #136941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136941	2019-07-26T15:46:48 Z	rondojim	Simurgh (IOI17_simurgh)	C++17	51 / 100	275 ms	4164 KB

simurgh

#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,tim;
ll X[125050];
ll Y[125050];
ll b[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(r[ii]);
		}
	ll mi=tim,ya=0,ma=-1;
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
			if(b[ii]==1)
			{
				r[aa]=ii;
				return ;
			}
		}
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
	//		cout<<aa<<" "<<ii<<"\n";
			//b[ii]=1;
			if(b[ii]==2)
				continue;
			tan.pb(ii);
			ll tom=count_common_roads(tan);
			mi=min(mi,tom);
			tan.pop_back();
			isi.pb(mp(-tom,ii));
			/*
			if(tom>mi)
			{
	//			ya=1;
				break;
			}*/
		}
//	cout<<aa<<" "<<ya<<"\n";
	//if(!ya)
	//	return ;
	if(isi.empty())
		return ;
	sort(isi.begin(),isi.end());
	for(ii=0;ii<isi.size();ii++)
		if(isi[0].fi==isi[ii].fi)
			b[isi[ii].se]=1;
		else
			b[isi[ii].se]=2;
	r[aa]=isi[0].se;
	tim=-isi[0].fi;
}
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);
		}
	//while(1);
	tim=count_common_roads(r);
	for(i=0;i<r.size();i++)
	{
		isi.clear();
		cek(i);
	//	cout<<i<<" "<<r[i]<<"\n";
	}
	//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:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<isi.size();ii++)
           ~~^~~~~~~~~~~
simurgh.cpp:33:12: warning: unused variable 'ya' [-Wunused-variable]
  ll mi=tim,ya=0,ma=-1;
            ^~
simurgh.cpp:33:17: warning: unused variable 'ma' [-Wunused-variable]
  ll mi=tim,ya=0,ma=-1;
                 ^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:93:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++)
          ~^~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	376 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	380 KB	correct
6	Correct	2 ms	376 KB	correct
7	Correct	2 ms	376 KB	correct
8	Correct	2 ms	376 KB	correct
9	Correct	2 ms	376 KB	correct
10	Correct	2 ms	376 KB	correct
11	Correct	2 ms	376 KB	correct
12	Correct	2 ms	376 KB	correct
13	Correct	2 ms	376 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	376 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	380 KB	correct
6	Correct	2 ms	376 KB	correct
7	Correct	2 ms	376 KB	correct
8	Correct	2 ms	376 KB	correct
9	Correct	2 ms	376 KB	correct
10	Correct	2 ms	376 KB	correct
11	Correct	2 ms	376 KB	correct
12	Correct	2 ms	376 KB	correct
13	Correct	2 ms	376 KB	correct
14	Correct	4 ms	376 KB	correct
15	Correct	4 ms	376 KB	correct
16	Correct	4 ms	376 KB	correct
17	Correct	4 ms	376 KB	correct
18	Correct	3 ms	376 KB	correct
19	Correct	4 ms	376 KB	correct
20	Correct	4 ms	376 KB	correct
21	Correct	4 ms	376 KB	correct
22	Correct	4 ms	376 KB	correct
23	Correct	4 ms	376 KB	correct
24	Correct	3 ms	376 KB	correct
25	Correct	2 ms	376 KB	correct
26	Correct	4 ms	376 KB	correct
27	Correct	4 ms	504 KB	correct
28	Correct	3 ms	376 KB	correct
29	Correct	3 ms	376 KB	correct
30	Correct	4 ms	376 KB	correct
31	Correct	4 ms	504 KB	correct
32	Correct	4 ms	376 KB	correct
33	Correct	4 ms	376 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	376 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	380 KB	correct
6	Correct	2 ms	376 KB	correct
7	Correct	2 ms	376 KB	correct
8	Correct	2 ms	376 KB	correct
9	Correct	2 ms	376 KB	correct
10	Correct	2 ms	376 KB	correct
11	Correct	2 ms	376 KB	correct
12	Correct	2 ms	376 KB	correct
13	Correct	2 ms	376 KB	correct
14	Correct	4 ms	376 KB	correct
15	Correct	4 ms	376 KB	correct
16	Correct	4 ms	376 KB	correct
17	Correct	4 ms	376 KB	correct
18	Correct	3 ms	376 KB	correct
19	Correct	4 ms	376 KB	correct
20	Correct	4 ms	376 KB	correct
21	Correct	4 ms	376 KB	correct
22	Correct	4 ms	376 KB	correct
23	Correct	4 ms	376 KB	correct
24	Correct	3 ms	376 KB	correct
25	Correct	2 ms	376 KB	correct
26	Correct	4 ms	376 KB	correct
27	Correct	4 ms	504 KB	correct
28	Correct	3 ms	376 KB	correct
29	Correct	3 ms	376 KB	correct
30	Correct	4 ms	376 KB	correct
31	Correct	4 ms	504 KB	correct
32	Correct	4 ms	376 KB	correct
33	Correct	4 ms	376 KB	correct
34	Correct	234 ms	1820 KB	correct
35	Correct	275 ms	2036 KB	correct
36	Correct	159 ms	1388 KB	correct
37	Correct	14 ms	376 KB	correct
38	Correct	221 ms	1756 KB	correct
39	Correct	212 ms	1656 KB	correct
40	Correct	162 ms	1444 KB	correct
41	Correct	98 ms	2040 KB	correct
42	Correct	214 ms	1912 KB	correct
43	Correct	149 ms	1272 KB	correct
44	Correct	165 ms	1044 KB	correct
45	Correct	146 ms	1136 KB	correct
46	Correct	110 ms	932 KB	correct
47	Correct	47 ms	632 KB	correct
48	Correct	7 ms	376 KB	correct
49	Correct	16 ms	376 KB	correct
50	Correct	48 ms	632 KB	correct
51	Correct	147 ms	1244 KB	correct
52	Correct	123 ms	988 KB	correct
53	Correct	113 ms	888 KB	correct
54	Correct	156 ms	1144 KB	correct
55	Correct	138 ms	1224 KB	correct
56	Correct	134 ms	1144 KB	correct
57	Correct	133 ms	1148 KB	correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	376 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	380 KB	correct
6	Correct	2 ms	376 KB	correct
7	Correct	2 ms	376 KB	correct
8	Correct	2 ms	376 KB	correct
9	Correct	2 ms	376 KB	correct
10	Correct	2 ms	376 KB	correct
11	Correct	2 ms	376 KB	correct
12	Correct	2 ms	376 KB	correct
13	Correct	2 ms	376 KB	correct
14	Correct	4 ms	376 KB	correct
15	Correct	4 ms	376 KB	correct
16	Correct	4 ms	376 KB	correct
17	Correct	4 ms	376 KB	correct
18	Correct	3 ms	376 KB	correct
19	Correct	4 ms	376 KB	correct
20	Correct	4 ms	376 KB	correct
21	Correct	4 ms	376 KB	correct
22	Correct	4 ms	376 KB	correct
23	Correct	4 ms	376 KB	correct
24	Correct	3 ms	376 KB	correct
25	Correct	2 ms	376 KB	correct
26	Correct	4 ms	376 KB	correct
27	Correct	4 ms	504 KB	correct
28	Correct	3 ms	376 KB	correct
29	Correct	3 ms	376 KB	correct
30	Correct	4 ms	376 KB	correct
31	Correct	4 ms	504 KB	correct
32	Correct	4 ms	376 KB	correct
33	Correct	4 ms	376 KB	correct
34	Correct	234 ms	1820 KB	correct
35	Correct	275 ms	2036 KB	correct
36	Correct	159 ms	1388 KB	correct
37	Correct	14 ms	376 KB	correct
38	Correct	221 ms	1756 KB	correct
39	Correct	212 ms	1656 KB	correct
40	Correct	162 ms	1444 KB	correct
41	Correct	98 ms	2040 KB	correct
42	Correct	214 ms	1912 KB	correct
43	Correct	149 ms	1272 KB	correct
44	Correct	165 ms	1044 KB	correct
45	Correct	146 ms	1136 KB	correct
46	Correct	110 ms	932 KB	correct
47	Correct	47 ms	632 KB	correct
48	Correct	7 ms	376 KB	correct
49	Correct	16 ms	376 KB	correct
50	Correct	48 ms	632 KB	correct
51	Correct	147 ms	1244 KB	correct
52	Correct	123 ms	988 KB	correct
53	Correct	113 ms	888 KB	correct
54	Correct	156 ms	1144 KB	correct
55	Correct	138 ms	1224 KB	correct
56	Correct	134 ms	1144 KB	correct
57	Correct	133 ms	1148 KB	correct
58	Correct	2 ms	376 KB	correct
59	Correct	2 ms	376 KB	correct
60	Incorrect	171 ms	4164 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #136941

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0