답안 #73731 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73731	2018-08-28T19:35:18 Z	hamzqq9	Simurgh (IOI17_simurgh)	C++14	51 / 100	264 ms	5488 KB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
#define ii pair<int,int>
#define st first
#define nd second
#define pb push_back
#define iii pair<ii,int>
#define all(x) x.begin(),x.end()
#define ppb pop_back
#define ll long long
#define sz(x) ((int)x.size())
using namespace std;

int n,m,inus,ous;
int normal;
vector<int> inmst,path,ans;
int pos[505*505];
int ata[505],ok[505*505];
vector<iii> rem,e;
vector<ii> v[505];
int flag,reach;

int bul(int x) {

	if(ata[x]==x) return x;

	return ata[x]=bul(ata[x]);

}

void finish(int w) {

	/*for(int i=0;i<sz(path);i++) cerr<<path[i]<<' ';

	cerr<<"\n-------------------\n";*/

	int bef=0;

	vector<int> ress;

	for(int i=0;i<sz(path);i++) {

		if(bef && ok[path[i]]!=0) {

			continue ;

		}

		bef=max(bef,ok[path[i]]);

		swap(inmst[pos[path[i]]],w);

		int cur=count_common_roads(inmst);

		swap(inmst[pos[path[i]]],w);

		/*if(w==2 && path[i]==6) {

			//cerr<<"spe   "<<normal<<' '<<cur<<'\n'<<pos[6]<<'\n';
/
			/(int j=0;j<sz(inmst);j++) cerr<<inmst[j]<<" ";

			cerr<<endl;

		}*/

		ress.pb(cur);

		if(cur>normal || (ok[path[i]]==1 && cur==normal)) {

			flag=1;

		}


		if(cur<normal || (ok[path[i]]==2 && cur==normal)) {

			flag=-1;

		}

	}

	int pr=0;
	int okk=0;

	if(flag==1) {

		for(int i=0;i<sz(path);i++) {

			if(ok[path[i]] && okk) continue ;

			okk+=ok[path[i]];

			if(ress[pr]==normal && !ok[path[i]]) {

				ok[path[i]]=1;

				ans.pb(path[i]);

			}
			else if(!ok[path[i]]) {

				ok[path[i]]=2;

			}

			++pr;

		}

	}
	else if(flag==-1) {

		for(int i=0;i<sz(path);i++) {

			if(ok[path[i]] && okk) continue ;

			okk+=ok[path[i]];

			if(ress[pr]==normal && !ok[path[i]]) {

				ok[path[i]]=2;

			}
			else if(!ok[path[i]]) {

				ok[path[i]]=1;
				ans.pb(path[i]);

			}

			++pr;

		}

		flag=0;

	}  
	else {

		for(int i=0;i<sz(path);i++) {

			ok[path[i]]=2;

		}

	}

}

void dfs(int node,int ata,int to,int w) {

	if(reach) return ;

	if(node==to) {

		finish(w);

		reach=1;

		return ;

	}

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		path.pb(i.nd);

		dfs(i.st,node,to,w);

		path.ppb();

	}

}

void make_mst() {

	for(int i=0;i<n;i++) ata[i]=i;

	for(auto i:e) {

		if(bul(i.st.st)!=bul(i.st.nd)) {

			inmst.pb(i.nd);

			pos[i.nd]=sz(inmst)-1;

			//cerr<<i.nd<<' '<<pos[i.nd]<<endl;

			ata[bul(i.st.st)]=bul(i.st.nd);

			v[i.st.st].pb({i.st.nd,i.nd});
			v[i.st.nd].pb({i.st.st,i.nd});

		}
		else {

			rem.pb(i);

		}

	}

	normal=count_common_roads(inmst);

}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	
	m=sz(u);
	::n=n;

	for(int i=0;i<m;i++) {

		e.pb({{u[i],v[i]},i});

	}

	random_shuffle(all(e));

	make_mst();

	//cerr<<normal<<endl;

	//cerr<<"----------------\n";

	//for(int i=0;i<sz(inmst);i++) cerr<<inmst[i]<<' ';

	//cerr<<"---------------\n";

	for(auto edge:rem) {

		flag=0;
		reach=0;

		//cerr<<edge.nd<<endl;

		dfs(edge.st.st,-1,edge.st.nd,edge.nd);

		if(flag) {

			//cerr<<"OK-->"<<edge.nd<<endl;

			ans.pb(edge.nd);

		}

		if(sz(ans)==n-1) break ;

	}

	//cerr<<"-----------------\n";

	for(int i=0;i<sz(inmst);i++) if(sz(ans)!=n-1 && !ok[inmst[i]]) ans.pb(inmst[i]);

	return ans;

}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	correct
2	Correct	3 ms	356 KB	correct
3	Correct	3 ms	560 KB	correct
4	Correct	2 ms	560 KB	correct
5	Correct	2 ms	560 KB	correct
6	Correct	2 ms	672 KB	correct
7	Correct	2 ms	672 KB	correct
8	Correct	3 ms	672 KB	correct
9	Correct	2 ms	672 KB	correct
10	Correct	2 ms	672 KB	correct
11	Correct	2 ms	672 KB	correct
12	Correct	2 ms	672 KB	correct
13	Correct	3 ms	672 KB	correct
14	Correct	4 ms	672 KB	correct
15	Correct	4 ms	672 KB	correct
16	Correct	5 ms	672 KB	correct
17	Correct	4 ms	672 KB	correct
18	Correct	4 ms	672 KB	correct
19	Correct	5 ms	672 KB	correct
20	Correct	4 ms	672 KB	correct
21	Correct	5 ms	672 KB	correct
22	Correct	5 ms	672 KB	correct
23	Correct	4 ms	684 KB	correct
24	Correct	3 ms	752 KB	correct
25	Correct	2 ms	752 KB	correct
26	Correct	4 ms	752 KB	correct
27	Correct	6 ms	752 KB	correct
28	Correct	3 ms	752 KB	correct
29	Correct	4 ms	752 KB	correct
30	Correct	4 ms	752 KB	correct
31	Correct	4 ms	752 KB	correct
32	Correct	4 ms	752 KB	correct
33	Correct	5 ms	752 KB	correct
34	Correct	211 ms	2048 KB	correct
35	Correct	194 ms	2048 KB	correct
36	Correct	140 ms	2048 KB	correct
37	Correct	11 ms	2048 KB	correct
38	Correct	264 ms	2048 KB	correct
39	Correct	179 ms	2048 KB	correct
40	Correct	129 ms	2048 KB	correct
41	Correct	218 ms	2164 KB	correct
42	Correct	196 ms	2164 KB	correct
43	Correct	128 ms	2164 KB	correct
44	Correct	83 ms	2164 KB	correct
45	Correct	127 ms	2164 KB	correct
46	Correct	66 ms	2164 KB	correct
47	Correct	27 ms	2164 KB	correct
48	Correct	4 ms	2164 KB	correct
49	Correct	10 ms	2164 KB	correct
50	Correct	26 ms	2164 KB	correct
51	Correct	94 ms	2164 KB	correct
52	Correct	96 ms	2164 KB	correct
53	Correct	82 ms	2164 KB	correct
54	Correct	113 ms	2164 KB	correct
55	Correct	144 ms	2164 KB	correct
56	Correct	112 ms	2164 KB	correct
57	Correct	104 ms	2164 KB	correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	correct
2	Correct	3 ms	356 KB	correct
3	Correct	3 ms	560 KB	correct
4	Correct	2 ms	560 KB	correct
5	Correct	2 ms	560 KB	correct
6	Correct	2 ms	672 KB	correct
7	Correct	2 ms	672 KB	correct
8	Correct	3 ms	672 KB	correct
9	Correct	2 ms	672 KB	correct
10	Correct	2 ms	672 KB	correct
11	Correct	2 ms	672 KB	correct
12	Correct	2 ms	672 KB	correct
13	Correct	3 ms	672 KB	correct
14	Correct	4 ms	672 KB	correct
15	Correct	4 ms	672 KB	correct
16	Correct	5 ms	672 KB	correct
17	Correct	4 ms	672 KB	correct
18	Correct	4 ms	672 KB	correct
19	Correct	5 ms	672 KB	correct
20	Correct	4 ms	672 KB	correct
21	Correct	5 ms	672 KB	correct
22	Correct	5 ms	672 KB	correct
23	Correct	4 ms	684 KB	correct
24	Correct	3 ms	752 KB	correct
25	Correct	2 ms	752 KB	correct
26	Correct	4 ms	752 KB	correct
27	Correct	6 ms	752 KB	correct
28	Correct	3 ms	752 KB	correct
29	Correct	4 ms	752 KB	correct
30	Correct	4 ms	752 KB	correct
31	Correct	4 ms	752 KB	correct
32	Correct	4 ms	752 KB	correct
33	Correct	5 ms	752 KB	correct
34	Correct	211 ms	2048 KB	correct
35	Correct	194 ms	2048 KB	correct
36	Correct	140 ms	2048 KB	correct
37	Correct	11 ms	2048 KB	correct
38	Correct	264 ms	2048 KB	correct
39	Correct	179 ms	2048 KB	correct
40	Correct	129 ms	2048 KB	correct
41	Correct	218 ms	2164 KB	correct
42	Correct	196 ms	2164 KB	correct
43	Correct	128 ms	2164 KB	correct
44	Correct	83 ms	2164 KB	correct
45	Correct	127 ms	2164 KB	correct
46	Correct	66 ms	2164 KB	correct
47	Correct	27 ms	2164 KB	correct
48	Correct	4 ms	2164 KB	correct
49	Correct	10 ms	2164 KB	correct
50	Correct	26 ms	2164 KB	correct
51	Correct	94 ms	2164 KB	correct
52	Correct	96 ms	2164 KB	correct
53	Correct	82 ms	2164 KB	correct
54	Correct	113 ms	2164 KB	correct
55	Correct	144 ms	2164 KB	correct
56	Correct	112 ms	2164 KB	correct
57	Correct	104 ms	2164 KB	correct
58	Correct	2 ms	2164 KB	correct
59	Correct	2 ms	2164 KB	correct
60	Incorrect	171 ms	5488 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #73731

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