oj.uz

Submission #594436

# Submission time Handle Problem Language Result Execution time Memory
594436 2022-07-12T12:46:59 Z FatihSolak Simurgh (IOI17_simurgh) C++17
30 / 100
 689 ms 32388 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];
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){
			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]);
				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 0 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 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 0 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 340 KB correct
14 Correct 44 ms 2708 KB correct
15 Correct 25 ms 1492 KB correct
16 Correct 24 ms 1492 KB correct
17 Correct 40 ms 2256 KB correct
18 Correct 11 ms 1012 KB correct
19 Correct 38 ms 2324 KB correct
20 Correct 42 ms 2136 KB correct
21 Correct 32 ms 1796 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 0 ms 340 KB correct
26 Correct 0 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 0 ms 340 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 0 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 340 KB correct
14 Correct 44 ms 2708 KB correct
15 Correct 25 ms 1492 KB correct
16 Correct 24 ms 1492 KB correct
17 Correct 40 ms 2256 KB correct
18 Correct 11 ms 1012 KB correct
19 Correct 38 ms 2324 KB correct
20 Correct 42 ms 2136 KB correct
21 Correct 32 ms 1796 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 0 ms 340 KB correct
26 Correct 0 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 0 ms 340 KB correct
33 Correct 1 ms 340 KB correct
34 Incorrect 689 ms 32388 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 489 ms 22464 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 0 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 340 KB correct
14 Correct 44 ms 2708 KB correct
15 Correct 25 ms 1492 KB correct
16 Correct 24 ms 1492 KB correct
17 Correct 40 ms 2256 KB correct
18 Correct 11 ms 1012 KB correct
19 Correct 38 ms 2324 KB correct
20 Correct 42 ms 2136 KB correct
21 Correct 32 ms 1796 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 0 ms 340 KB correct
26 Correct 0 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 0 ms 340 KB correct
33 Correct 1 ms 340 KB correct
34 Incorrect 689 ms 32388 KB WA in grader: NO
35 Halted 0 ms 0 KB -