Submission #1048411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048411		Alihan_8	Highway Tolls (IOI18_highway)	C++17	51 / 100	117 ms	26712 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

using namespace std;

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

using i64 = long long;

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

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

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int n = N, 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> w(m);
	
	i64 C = ask(w);
	
	int l = 0, r = m - 1;
	
	while ( l < r ){
		int md = (l + r) / 2;
		
		w.assign(m, 0);
		
		for ( int i = 0; i <= md; i++ ){
			w[i] = 1;
		}
		
		if ( ask(w) != C ){
			r = md;
		} else l = md + 1;
	}
	
	vector <vector<ar<int,2>>> tree(n);
	
	auto bfs = [&](int sx){
		vector <int> d(n, n + 1); 
		
		for ( auto &x: tree ){
			x.clear();
		}
		
		queue <int> q;
		
		q.push(sx); d[sx] = 0;
		
		while ( !q.empty() ){
			int u = q.front();
			q.pop();
			
			for ( auto &[v, j]: adj[u] ){
				if ( chmin(d[v], d[u] + 1) ){
 					q.push(v); 
					
					tree[u].pb({v, j});
				}
			}
		}
		
		return d;
	};
	
	auto d1 = bfs(U[l]); auto g1 = tree;
	auto d2 = bfs(V[l]); auto g2 = tree;
	
	int E = l;
	
	auto get = [&](int sx){
		vector <int> e, ord;
		
		auto dfs = [&](auto dfs, int u) -> void{
			ord.pb(u);
			
			for ( auto &[v, j]: g1[u] ){
				if ( d1[v] >= d2[v] ){
					continue;
				}
				
				e.pb(j);
				
				dfs(dfs, v);
			}
		};
		
		dfs(dfs, sx);
		
		w.assign(m, 1);
		
		for ( auto &j: e ) w[j] = 0;
		w[E] = 0;
		
		i64 T = ask(w);
		
		int l = 0, r = (int)e.size();
		
		while ( l < r ){
			int md = (l + r) / 2;
			
			w.assign(m, 1);
			
			for ( int i = 0; i < (int)e.size(); i++ ){
				w[e[i]] = !(i < md);
			} w[E] = 0;
			
			if ( ask(w) == T ){
				r = md;
			} else l = md + 1;
		}
		
		return ord[l];
	};
	
 	int x = get(U[l]); 
	
	swap(d1, d2), swap(g1, g2);
	
	int y = get(V[l]);
	
	answer(x, y);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31