Submission #858842

#	Time	Username	Problem	Language	Result	Execution time	Memory
858842		waldi	Highway Tolls (IOI18_highway)	C++17	51 / 100	115 ms	14164 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void find_pair(int n, vector<int> u, vector<int> v, int a_int, int b_int){
	int m = u.size();
	ll a = a_int, b = b_int;
	vector<vector<pii>> g(n);
	REP(i, m){
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}
	
	if(m == n-1){
		vector<int> pyt(m, 0);
		ll samea = ask(pyt);
		
		int kr = 0;
		for(int lewo = 0, prawo = m-1; 1;){
			if(lewo == prawo){kr = lewo; break;}
			int sr = (lewo+prawo)>>1;
			pyt = vector<int>(m, 0);
			FOR(i, lewo, sr) pyt[i] = 1;
			if(ask(pyt) > samea) prawo = sr;
			else lewo = sr+1;
		}
		int x = u[kr], y = v[kr];
		
		pyt = vector<int>(m, 0);
		function<void(int, int)> dfs_oznacz = [&](int w, int o){
			for(pii i : g[w]) if(i.fi != o) pyt[i.se] = 1, dfs_oznacz(i.fi, w);
		};
		dfs_oznacz(x, y);
		int dlx = (ask(pyt)-samea)/(b-a);
		int dly = samea/a - dlx-1;
		
		vector<pii> vec;
		function<void(int, int, int, int)> dfs_gl = [&](int w, int o, int gl, int id){
			if(!gl) return void(vec.emplace_back(id, w));
			for(pii i : g[w]) if(i.fi != o) dfs_gl(i.fi, w, gl-1, i.se);
		};
		
		dfs_gl(x, y, dlx, kr);
		int s = 0;
		for(int lewo = 0, prawo = vec.size()-1; 1;){
			if(lewo == prawo){s = vec[lewo].se; break;}
			int sr = (lewo+prawo)>>1;
			pyt = vector<int>(m, 0);
			FOR(i, lewo, sr) pyt[vec[i].fi] = 1;
			if(ask(pyt) > samea) prawo = sr;
			else lewo = sr+1;
		}
		
		vec.clear();
		dfs_gl(y, x, dly, kr);
		int t = 0;
		for(int lewo = 0, prawo = vec.size()-1; 1;){
			if(lewo == prawo){t = vec[lewo].se; break;}
			int sr = (lewo+prawo)>>1;
			pyt = vector<int>(m, 0);
			FOR(i, lewo, sr) pyt[vec[i].fi] = 1;
			if(ask(pyt) > samea) prawo = sr;
			else lewo = sr+1;
		}
		
		answer(s, t);
	}
}

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