oj.uz

답안 #594489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594489 2022-07-12T14:31:51 Z FatihSolak Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 596 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define N 500
using namespace std;
int deg[N];
set<int> adj2[N];
set<int> adj[N];
int edge[N][N];
int par[N];
bool can[N*N];
int 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;
		in_answer[i] = -1;
		edge[u[i]][v[i]] = i;
		edge[v[i]][u[i]] = i;
	}
	if(n >= 4 && m == n * (n-1) / 2){
		vector<int> ans;
		for(int i = 0;i<n;i++){
			set<int> s;
			for(int j = 0;j<n;j++){
				if(i == j)continue;
				s.insert(edge[i][j]);
			}
			deg[i] = get(s);
			if(i == 0){
				for(int j = 1;j<n;j++){
					int num = 1;
					if(j == 1)num = 2;
					s.erase(edge[i][j]);
					s.insert(edge[j][num]);
					if(get(s) < deg[i]){
						adj2[i].insert(j);
						adj2[j].insert(i);
						ans.push_back(edge[i][j]);
					}
					s.insert(edge[i][j]);
					s.erase(edge[j][num]);
				}
			}
		}
		assert(deg[0] == adj2[0].size());
		for(int i = 1;i<n;i++){
			vector<int> points;
			for(int j = 0;j<n;j++){
				if(i == j)continue;
				points.push_back(j);
			}
			while(adj2[i].size() != deg[i]){
				int l = 0, r= n-1;
				while(points[l] <= i || (adj2[i].size() && points[l] <= *adj2[i].rbegin())){
					l++;
				}
				while(l < r){
					int m = (l + r)/2;
					int cnt = 0;
					set<int> s;
					for(int j = 0;j<n-1;j++){
						if(l <= j && j <= m){
							s.insert(edge[points[j]][0]);
							cnt += adj2[0].count(points[j]);
						}
						else{
							s.insert(edge[i][points[j]]);
						}
					}
					if(get(s) - cnt < deg[i]){
						r = m;
					}
					else l = m + 1;
				}
				adj2[i].insert(points[l]);
				adj2[points[l]].insert(i);
				ans.push_back(edge[i][points[l]]);
			}
		}
		return ans;
	}
	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;
		// cout << last << endl;
		vector<int> known;
		vector<int> unknown;
		for(auto x:edges){
			if(in_answer[x] == -1){
				unknown.push_back(x);
			}
			else known.push_back(x);
		}
		bool add_cur = 0;
		for(auto x:unknown){
			r.erase(x);
			r.insert(last);
			if(get(r) > best){
				add_cur = 1;
			}
			r.erase(last);
			r.insert(x);
		}
		if(known.size()){
			r.erase(known[0]);
			r.insert(last);
			if(get(r) > best - in_answer[known[0]]){
				add_cur = 1;
			}
			r.erase(last);
			r.insert(known[0]);
		}
		for(auto x:unknown){
			r.erase(x);
			r.insert(last);
			if(best - (get(r) - add_cur) > 0){
				in_answer[x] = 1;
			}
			else in_answer[x] = 0;
			r.erase(last);
			r.insert(x);
		}
		if(add_cur){
			for(auto x:edges){
				if(in_answer[x] == 0){
					r.erase(x);
				r.insert(last);
					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;
				}
			}
		}
		last++;
	}
	vector<int> ret;
	for(auto u:r){
		ret.push_back(u);
	}
	return ret;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   assert(deg[0] == adj2[0].size());
      |          ~~~~~~~^~~~~~~~~~~~~~~~~
simurgh.cpp:95:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |    while(adj2[i].size() != deg[i]){
      |          ~~~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB correct
2 Runtime error 1 ms 596 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -