oj.uz

Submission #399784

# Submission time Handle Problem Language Result Execution time Memory
399784 2021-05-06T15:27:47 Z kshitij_sodani Simurgh (IOI17_simurgh) C++14
30 / 100
 254 ms 3752 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
#define ask count_common_roads
#include "simurgh.h"
int par[501];
vector<pair<int,int>> adj[501];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int ca=-1;
vector<int> pp;
vector<int> pp2;
void dfs(int no,int par2=-1){
	if(no==ca){
		pp2=pp;
	}
	for(auto j:adj[no]){
		if(j.a!=par2){
			pp.pb(j.b);
			dfs(j.a,no);
			pp.pop_back();
		}
	}
}
vector<int> find_roads(int n,vector<int> uu,vector<int> vv) {
	int m=uu.size();
	for(int i=0;i<n;i++){
		par[i]=i;
	}
	vector<pair<pair<int,int>,int>> cur;
	vector<pair<pair<int,int>,int>> cur2;
	for(int i=0;i<m;i++){
		int x=find(uu[i]);
		int y=find(vv[i]);
		if(x!=y){
			par[x]=y;
			cur.pb({{uu[i],vv[i]},i});
		}
		else{
			cur2.pb({{uu[i],vv[i]},i});
		}
	}
	mt19937 rng;
	rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
	int val;
	vector<int> ee;
	for(auto j:cur){
		ee.pb(j.b);
	}
	val=ask(ee);
	/*for(auto j:ee){
		cout<<j<<",";
	}
	cout<<endl;*/
	shuffle(cur2.begin(),cur2.end(),rng);
	for(auto j:cur2){
		if(val==n-1){
			break;
		}
		for(int i=0;i<n;i++){
			adj[i].clear();
		}
		for(auto i:cur){
			adj[i.a.a].pb({i.a.b,i.b});
			adj[i.a.b].pb({i.a.a,i.b});
		}
		ca=j.a.b;
		dfs(j.a.a);
		shuffle(pp2.begin(),pp2.end(),rng);
		for(auto i:pp2){
			/*if(j.b==4){
				cout<<i<<"<<"<<endl;
			}*/
			vector<int> ff;
			for(auto jj:ee){
				if(jj!=i){
					ff.pb(jj);
				}
			}
			ff.pb(j.b);
			int val2=ask(ff);
			/*
			if(j.b==4){
				for(auto j:ff){
					cout<<j<<".";
				}
			
				cout<<endl;
				cout<<val<<"::"<<endl;
				cout<<val2<<"::"<<endl;
			}*/
			if(val2<val){
				break;
			}
			if(val2==val){
				continue;
			}
			vector<pair<pair<int,int>,int>> cur3;
			for(auto ii:cur){
				if(ii.b==i){
					continue;
				}
				cur3.pb(ii);
			}
			cur3.pb(j);
			cur=cur3;
			val=val2;
			ee=ff;
			/*for(auto j:ff){
				cout<<j<<",";
			}
			cout<<endl;*/

			break;
		}


	}
	return ee;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 324 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 208 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 324 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 208 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 6 ms 320 KB correct
15 Correct 7 ms 332 KB correct
16 Correct 6 ms 388 KB correct
17 Correct 6 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 6 ms 332 KB correct
20 Correct 5 ms 312 KB correct
21 Correct 5 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 308 KB correct
25 Correct 1 ms 312 KB correct
26 Correct 1 ms 308 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 308 KB correct
31 Correct 1 ms 332 KB correct
32 Correct 1 ms 332 KB correct
33 Correct 1 ms 332 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 324 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 208 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 6 ms 320 KB correct
15 Correct 7 ms 332 KB correct
16 Correct 6 ms 388 KB correct
17 Correct 6 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 6 ms 332 KB correct
20 Correct 5 ms 312 KB correct
21 Correct 5 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 308 KB correct
25 Correct 1 ms 312 KB correct
26 Correct 1 ms 308 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 308 KB correct
31 Correct 1 ms 332 KB correct
32 Correct 1 ms 332 KB correct
33 Correct 1 ms 332 KB correct
34 Incorrect 254 ms 1436 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Incorrect 178 ms 3752 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 324 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 208 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 6 ms 320 KB correct
15 Correct 7 ms 332 KB correct
16 Correct 6 ms 388 KB correct
17 Correct 6 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 6 ms 332 KB correct
20 Correct 5 ms 312 KB correct
21 Correct 5 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 308 KB correct
25 Correct 1 ms 312 KB correct
26 Correct 1 ms 308 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 308 KB correct
31 Correct 1 ms 332 KB correct
32 Correct 1 ms 332 KB correct
33 Correct 1 ms 332 KB correct
34 Incorrect 254 ms 1436 KB WA in grader: NO
35 Halted 0 ms 0 KB -