Submission #1043828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043828		Mr_Husanboy	Simurgh (IOI17_simurgh)	C++17	30 / 100	71 ms	2020 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
 
#define ll long long
 
template<typename T>
int len(T &a){
	return a.size();
}
 
struct DSU{
	vector<int> par, sz; int n;
	DSU (int _n){
		n = _n;
		par.resize(n);
		iota(all(par), 0);
		sz.assign(n, 1);
	}
	DSU (){}
	int get(int a){
		return (par[a] == a ? a : par[a] = get(par[a]));
	}
 
	void init(int _n){
		n = _n;
		par.resize(n);
		iota(all(par), 0);
		sz.assign(n, 1);
	}
 
	void unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a,b);
		sz[a] += sz[b];
		par[b] = a;
	}
 
	void link(int a, int b){
		a = get(a); b = get(b);
		if(a == b) return;
		sz[b] += sz[a];
		par[a] = b;
	}
};
 
 int _qu = 0;
int ask(const vector<int> &gs){
	_qu ++;
	assert(_qu <= 30000);
	return count_common_roads(gs);
}
 
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<int> royal;
	int m = len(u);
	DSU roy(n);
	vector<int> in(m);
	for(int i = 0; i < n - 1; i ++){
		DSU t(n);
		vector<int> gs;
		vector<int> rem;
		for(int j = 0; j < m; j ++){
			if(u[j] == i || v[j] == i){
				rem.push_back(j);
			}else{
				if(t.get(v[j]) == t.get(u[j])) continue;
				gs.push_back(j);
				t.unite(v[j], u[j]);
			}
		}
		vector<vector<int>> mp;
		map<int,int> id;
		for(auto j : rem){
			//cout<<j << ' ';
			int p = t.get(u[j] ^ v[j] ^ i);
			if(id.count(p) == 0){
				id[p] = len(id);
				mp.push_back(vector<int>());
			}
			mp[id[p]].push_back(j);
		}
		for(int j = 0; j < len(mp); j ++){
			int f = -1;
			if(len(mp[j]) == 1){
				if(roy.get(u[mp[j][0]]) == roy.get(v[mp[j][0]])){
					continue;
				}
				royal.push_back(mp[j][0]);
				roy.unite(u[mp[j][0]], v[mp[j][0]]);
				in[mp[j][0]] = 1;
				continue;
			}else{
				for(int k = 0; k < len(mp); k ++){
					if(k == j){
						continue;
					}
					gs.push_back(mp[k][0]);
				}
				vector<pair<int,int>> counts;
				for(int k = 0; k < len(mp[j]); k ++){
					if(in[mp[j][k]]) {f = mp[j][k]; break;};
				}
				if(f == -1){
					int mx = 0;
					vector<pair<int,int>> counts;
					for(auto k : mp[j]){
						gs.push_back(k);
						int cnt = ask(gs);
						counts.push_back({cnt, k});
						gs.pop_back();
						if(cnt > mx){
							mx = cnt;
						}
					}
					for(auto [cnt, k] : counts){
						if(cnt == mx){
							royal.push_back(k);
							roy.unite(u[k], v[k]);
							in[k] =1;
						}
					}
				}else{
					gs.push_back(f);
					int mx = ask(gs);
					gs.pop_back();
					for(auto k : mp[j]){
						if(roy.get(u[k]) == roy.get(v[k])) continue;
						gs.push_back(k);
						if(ask(gs) == mx){
							royal.push_back(k);
							roy.unite(u[k], v[k]);
							in[k] = 1;
						}
						gs.pop_back();
					}
				}
 
				for(int k = 0; k < len(mp) - 1; k ++){
					gs.pop_back();
				}
			}
		}
	}
	assert(len(royal) == n - 1);
	return royal;
}

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