Submission #1052969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052969		Alihan_8	Simurgh (IOI17_simurgh)	C++17	100 / 100	616 ms	22352 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define ln '\n'

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

map <vector<int>,int> dp;

int qry(vector <int> x){
	sort(all(x));
	
	if ( !dp.count(x) ){
		dp[x] = count_common_roads(x);
	}
	
	return dp[x];
}

int ask(set <int> s){
	vector <int> x;
	
	for ( auto &u: s ) x.pb(u);
	
	return qry(x);
}

vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V){
	int m = U.size();
	
	vector <vector<ar<int,2>>> adj(n);
	
	for ( int i = 0; i < m; i++ ){
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	
	vector <int> f(m, -1), d(n, -1), is(m);
	vector <ar<int,2>> fa(n, {-1, -1}), b(n);
	
	auto dfs = [&](auto dfs, int u, int p) -> void{
		ar <int,2> back = {n + 1, -1};
	
		for ( auto &[v, j]: adj[u] ){
			if ( v != p ){
				if ( d[v] == -1 ){
					d[v] = d[u] + 1;
					fa[v] = {u, j};
					is[j] = 1;
					
					dfs(dfs, v, u);
				} else if ( d[v] < d[u] ){ 
					if ( back[1] == -1 || d[back[0]] > d[v] ){
						back = {v, j};
					}
				}
			}
		}
		
		b[u] = back;
	};
	
	d[0] = 0;
	
	dfs(dfs, 0, -1);
	
	set <int> et;
	
	for ( int i = 0; i < m; i++ ){
		if ( is[i] ) et.insert(i);
	}
	
	int C = ask(et);
	
	auto dfs2 = [&](auto dfs2, int u, int p) -> void{
		for ( auto &[v, j]: adj[u] ){
			if ( v != p && is[j] ){
				dfs2(dfs2, v, u);
			}
		}
		
		int j = fa[u][1];
		
		if ( j == -1 ) return;
		
		auto &bb = b[u];
		
		if ( bb[1] == -1 ){
			if ( f[j] == -1 ) f[j] = 1;
		} else{			
			vector <int> p;
			
			int v = u;
			
			while ( v != bb[0] ){
				p.pb(fa[v][1]);
				v = fa[v][0];
			}
			
			sort(all(p), [&](int &u, int &v){
				return f[u] > f[v];
			});
			
			vector <int> R;
			
			int tmp = -1;
			
			et.insert(bb[1]);
			
			for ( auto &j: p ){
				et.erase(j);
				
				if ( f[j] != -1 ){
					if ( tmp == -1 ){
						tmp = ask(et);
					
						if ( tmp == C ){
							f[bb[1]] = f[j];
						} else{
							f[bb[1]] = (tmp > C);
							assert(f[bb[1]] != f[j]);
						}
					}
				} else{
					int q = ask(et);
					
					if ( q == C ){
						R.pb(j); // f[j] == f[bb[1]]
					} else{
						f[bb[1]] = (q > C);
						f[j] = f[bb[1]] ^ 1;
					}
				}
				
				et.insert(j);
			}
			
			et.erase(bb[1]);
			
			if ( f[bb[1]] == -1 ){
				f[bb[1]] = 0;
			}
			
			for ( auto &x: R ) f[x] = f[bb[1]];
		}
	};
	
	dfs2(dfs2, 0, -1);
	
	for ( int root = 0; root < n; root++ ){
		vector <int> fa(n);
		
		auto dfs = [&](auto dfs, int u, int p) -> void{
			for ( auto &[v, j]: adj[u] ){
				if ( v != p && is[j] ){
					fa[v] = j;
					
					dfs(dfs, v, u);
				}
			}
		};
		
		dfs(dfs, root, -1);
		
		
		vector <ar<int,2>> p;
		
		for ( auto &[v, j]: adj[root] ){
			if ( f[j] == -1 ) p.pb({fa[v], j});
		}
		
		int it = 0, k = p.size();
		
		while ( it < k ){
			int l = it, r = k;
			
			auto ok = [&](int m){
				int tmp = C;
				
				for ( int j = it; j <= m; j++ ){
					et.insert(p[j][1]);
					et.erase(p[j][0]);
					
					tmp -= f[p[j][0]];
				}
				
				int q = ask(et);
				
				for ( int j = it; j <= m; j++ ){
					et.erase(p[j][1]);
					et.insert(p[j][0]);
				}
				
				return q != tmp;
			};
			
			while ( l < r ){
				int m = (l + r) / 2;
				
				if ( ok(m) ){
					r = m;
				} else l = m + 1;
			}
			
			for ( int j = it; j < l; j++ ){
				f[p[j][1]] = 0;
			}
			
			if ( l < k ) f[p[l][1]] = 1;
			
			it = l + 1;
		}
	}

	for ( auto &x: f ){
		assert(x != -1);
	}
	
	vector <int> ans;
	
	for ( int i = 0; i < m; i++ ){
		if ( f[i] ) ans.pb(i);
	}
	
	return ans;
}

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