oj.uz

답안 #594434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594434 2022-07-12T12:45:06 Z FatihSolak Simurgh (IOI17_simurgh) C++17
30 / 100
 46 ms 3556 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define N 50
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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 0 ms 308 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 304 KB correct
9 Correct 1 ms 312 KB correct
10 Correct 0 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 0 ms 308 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 304 KB correct
9 Correct 1 ms 312 KB correct
10 Correct 0 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 46 ms 2608 KB correct
15 Correct 25 ms 1356 KB correct
16 Correct 25 ms 1376 KB correct
17 Correct 35 ms 2144 KB correct
18 Correct 11 ms 924 KB correct
19 Correct 45 ms 2200 KB correct
20 Correct 33 ms 1856 KB correct
21 Correct 39 ms 1612 KB correct
22 Correct 1 ms 312 KB correct
23 Correct 1 ms 212 KB correct
24 Correct 1 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 1 ms 212 KB correct
27 Correct 1 ms 212 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 1 ms 212 KB correct
31 Correct 1 ms 212 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 212 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 0 ms 308 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 304 KB correct
9 Correct 1 ms 312 KB correct
10 Correct 0 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 46 ms 2608 KB correct
15 Correct 25 ms 1356 KB correct
16 Correct 25 ms 1376 KB correct
17 Correct 35 ms 2144 KB correct
18 Correct 11 ms 924 KB correct
19 Correct 45 ms 2200 KB correct
20 Correct 33 ms 1856 KB correct
21 Correct 39 ms 1612 KB correct
22 Correct 1 ms 312 KB correct
23 Correct 1 ms 212 KB correct
24 Correct 1 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 1 ms 212 KB correct
27 Correct 1 ms 212 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 1 ms 212 KB correct
31 Correct 1 ms 212 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 212 KB correct
34 Runtime error 6 ms 1492 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB correct
2 Correct 1 ms 308 KB correct
3 Runtime error 15 ms 3556 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 0 ms 308 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 304 KB correct
9 Correct 1 ms 312 KB correct
10 Correct 0 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 46 ms 2608 KB correct
15 Correct 25 ms 1356 KB correct
16 Correct 25 ms 1376 KB correct
17 Correct 35 ms 2144 KB correct
18 Correct 11 ms 924 KB correct
19 Correct 45 ms 2200 KB correct
20 Correct 33 ms 1856 KB correct
21 Correct 39 ms 1612 KB correct
22 Correct 1 ms 312 KB correct
23 Correct 1 ms 212 KB correct
24 Correct 1 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 1 ms 212 KB correct
27 Correct 1 ms 212 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 1 ms 212 KB correct
31 Correct 1 ms 212 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 212 KB correct
34 Runtime error 6 ms 1492 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -