Submission #1174885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174885		ThylOne	Simurgh (IOI17_simurgh)	C++20	0 / 100	61 ms	2752 KiB

simurgh

#include "simurgh.h"
#include <algorithm>
#include<bits/stdc++.h>
#include <unordered_map>

using namespace std;
struct UF{
	vector<int> chef;
	UF(int n){
		chef.resize(n);
		for(int i=0;i<n;i++)chef[i]=i;
	}
	int find(int a){
		if(chef[a]==a)return a;
		return chef[a] = find(chef[a]);
	}
	void fusion(int a, int b){
		a = find(a);
		b = find(b);
		if(a!=b){
			chef[a]=b;
		}
	}
};
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	vector<pair<int,int>> edges;
	for(int i= 0;i<u.size();i++){
		edges.push_back(make_pair(u[i], v[i]));
	}
	vector<int> re(u.size(),0);
	vector<bool> done(u.size(),false);
	vector<int> maxi(n,-n), mini(n,n+1);
	vector<int> golden[n];
	for(int node = 0 ; node < n ; node++){
		UF uf(n);
		vector<int> totest, spanning;
		for(int i=0;i<u.size();i++){
			auto e = edges[i];
			if(e.first != node && e.second != node){
				if(uf.find(e.first)!=uf.find(e.second)){
					uf.fusion(e.first,e.second);
					spanning.push_back(i);
				}
			}else{
				if(!done[i]){
					totest.push_back(i);
					done[i]=true;
				}
			}
		}
		if(golden[node].size()){
			totest.push_back(golden[node].back());
		}
		for(auto &t:totest){
			vector<int> cspanning(spanning);
			cspanning.push_back(t);
			re[t] = count_common_roads(cspanning);
			maxi[node] = max(maxi[node], re[t]);
		}
		
		for(auto &t:totest){
			if(re[t]==maxi[node]){
				golden[edges[t].first].push_back(t);
				golden[edges[t].second].push_back(t);
			}
		}

	}
	
	set<int> ans;
	for(int i=0;i<n;i++){
		for(int &u:golden[i]){
			ans.insert(u);
		}
	}
	vector<int> out;
	for(int u:ans)out.push_back(u);

	return out;
}

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