Submission #594481

#	Time	Username	Problem	Language	Result	Execution time	Memory
594481		FatihSolak	Simurgh (IOI17_simurgh)	C++17	51 / 100	1370 ms	31248 KiB

simurgh

#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 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;
	}
	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;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30