Submission #1089918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089918		vjudge1	Simurgh (IOI17_simurgh)	C++17	30 / 100	1706 ms	32084 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e4 + 20;

namespace DSU{
	int p[N];

	void init(int n){
		iota(p, p + n, 0);
	}

	int find(int u){
		if(u == p[u])return u;
		return p[u] = find(p[u]);
	}

	bool join(int u,int v){
		u = find(u), v = find(v);
		if(u == v)return 0;
		p[u] = v ;
		return 1;
	}
}

bool t[N], vis[N];

map<vector<int>, int> mp;
int qry(vector<int> v){
	sort(v.begin(), v.end());
	if(mp.count(v))return mp[v];
	return mp[v] = count_common_roads(v);
}

std::vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V) {
	int m = U.size();
	DSU::init(n);
	vector<int> ans;
	for(int i = 0;i < m;i++){
		if(DSU::join(U[i], V[i]))ans.push_back(i), t[i] = 1;
	}
	int res = qry(ans);
	for(int i = 0;i < m && res < n - 1;i++){
		if(!t[i] || vis[i])continue;
		int mj = i;
		for(int j = 0;j < m;j++){
			if(t[j] || vis[j])continue;
			vector<int> T;
			for (auto x: ans){
				if (x != i) T.push_back(x);
			}
			T.push_back(j);
			DSU::init(n);
			int cnt = 0;
			for (auto u: T){
				if(DSU::join(U[u],V[u]))cnt++;
			}
			if (cnt == n - 1){
				int h = qry(T);
				if (h <= res) continue;
				mj = j;
				t[mj] = 1;
				t[i] = 0;
				swap(ans, T);
				res = h;
				break;
			}
		}
		vis[i] = vis[mj] = 1;
	}
	return ans;
}

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