oj.uz

Submission #594437

# Submission time Handle Problem Language Result Execution time Memory
594437 2022-07-12T12:47:59 Z FatihSolak Simurgh (IOI17_simurgh) C++17
30 / 100
 683 ms 32272 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define N 500
using namespace std;
set<int> adj[N];
int edge[N][N];
int par[N];
bool can[N*N];
bool in_answer[N*N];
int find(int a){
	if(par[a] == a)return a;
	return par[a] = find(par[a]);
}
bool merge(int a,int b){
	a = find(a);
	b = find(b);
	if(a == b)
		return 0;
	par[b] = a;
	return 1;
}
vector<int> edges;
int dfspar[N];
void dfs(int v,int target,int pr){
	//cout << v << " " << target << " " << pr << endl;
	dfspar[v] = pr;
	if(v == target){
		while(dfspar[v] != -1){
			edges.push_back(edge[v][dfspar[v]]);
			v = dfspar[v];
		}
		return;
	}
	for(auto u:adj[v]){
		if(u == pr)continue;
		dfs(u,target,v);
	}
}
map<vector<int>,int> mp;
int get(set<int> s){
	vector<int> r;
	for(auto u:s)r.push_back(u);
	if(mp.count(r))
		return mp[r];
	return mp[r] = count_common_roads(r);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			edge[i][j] = -1;
		}
		par[i] = i;
	}
	for(int i = 0;i<m;i++){
		can[i] = 1;
		edge[u[i]][v[i]] = i;
		edge[v[i]][u[i]] = i;
	}
	set<int> r;
	//cout << endl;
	for(int i = 0;i<m;i++){
		//cout << u[i] << " " << v[i] << endl;
		if(merge(u[i],v[i])){
			//cout << i << endl;
			can[i] = 0;
			adj[u[i]].insert(v[i]);
			adj[v[i]].insert(u[i]);
			r.insert(i);
		}
	}
	// cout << "hey" << endl;
	// for(auto u:r){
	// 	cout << u << " ";
	// }
	// cout << endl;
	int last = 0;
	while(get(r) != n-1){
		while(!can[last])
			last++;
		//cout << "hey" << endl;
		int best = get(r);
		edges.clear();
		//cout << "hey" << endl;
		dfs(u[last],v[last],-1);
		// cout << "hey" << endl;
		// for(auto u:r){
		// 	cout << u << " ";
		// }
		// cout << endl;
		// for(auto x:edges){
		// 	cout << x << " ";
		// }
		// cout << endl;
		for(auto x:edges){
			if(in_answer[x])continue;
			r.erase(x);
			r.insert(last);
			if(get(r) > best){
				adj[u[x]].erase(v[x]);
				adj[v[x]].erase(u[x]);
				adj[u[last]].insert(v[last]);
				adj[v[last]].insert(u[last]);
				in_answer[last] = 1;
				break;
			}
			else{
				r.erase(last);
				r.insert(x);
			}
		}
		last++;
	}
	vector<int> ret;
	for(auto u:r){
		ret.push_back(u);
	}
	return ret;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 28 ms 1676 KB correct
15 Correct 15 ms 1012 KB correct
16 Correct 19 ms 980 KB correct
17 Correct 21 ms 1364 KB correct
18 Correct 8 ms 724 KB correct
19 Correct 29 ms 1452 KB correct
20 Correct 18 ms 1200 KB correct
21 Correct 16 ms 1152 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 0 ms 340 KB correct
24 Correct 0 ms 340 KB correct
25 Correct 0 ms 340 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 0 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 0 ms 340 KB correct
31 Correct 0 ms 340 KB correct
32 Correct 1 ms 420 KB correct
33 Correct 1 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 28 ms 1676 KB correct
15 Correct 15 ms 1012 KB correct
16 Correct 19 ms 980 KB correct
17 Correct 21 ms 1364 KB correct
18 Correct 8 ms 724 KB correct
19 Correct 29 ms 1452 KB correct
20 Correct 18 ms 1200 KB correct
21 Correct 16 ms 1152 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 0 ms 340 KB correct
24 Correct 0 ms 340 KB correct
25 Correct 0 ms 340 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 0 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 0 ms 340 KB correct
31 Correct 0 ms 340 KB correct
32 Correct 1 ms 420 KB correct
33 Correct 1 ms 340 KB correct
34 Incorrect 683 ms 32272 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 28 ms 1676 KB correct
15 Correct 15 ms 1012 KB correct
16 Correct 19 ms 980 KB correct
17 Correct 21 ms 1364 KB correct
18 Correct 8 ms 724 KB correct
19 Correct 29 ms 1452 KB correct
20 Correct 18 ms 1200 KB correct
21 Correct 16 ms 1152 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 0 ms 340 KB correct
24 Correct 0 ms 340 KB correct
25 Correct 0 ms 340 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 0 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 0 ms 340 KB correct
31 Correct 0 ms 340 KB correct
32 Correct 1 ms 420 KB correct
33 Correct 1 ms 340 KB correct
34 Incorrect 683 ms 32272 KB WA in grader: NO
35 Halted 0 ms 0 KB -