oj.uz

Submission #73731

# Submission time Handle Problem Language Result Execution time Memory
73731 2018-08-28T19:35:18 Z hamzqq9 Simurgh (IOI17_simurgh) C++14
51 / 100
 264 ms 5488 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -