Submission #1112341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112341		thelegendary08	Highway Tolls (IOI18_highway)	C++14	18 / 100	106 ms	8876 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vpii vector<pair<int,int>>
#define pb push_back
#define vvi vector<vector<int>>
#define ll long long int
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define pii pair<int,int>
using namespace std;
ll base;
ll len;
int a;
int b;
int m;
pii search(int l, int r){
	if(l == r)return{l, l};
	vi w(m,0);
	int mid = (l + r)/2;
	for(int i = l; i<=mid; i++)w[i] = 1;
	ll ret = ask(w);
	if(ret == base){
		return search(mid + 1, r);
	}
	else if(ret == len * b){
		return search(l, mid);
	}
	else{
		int cnt = (ret - base) / (b - a);
		return {mid - cnt+1, mid - cnt + len};
	}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	bool s3 = true;
	f0r(i, m){
		if(U[i] != i || V[i] != i+1)s3 = false;
	}
	a = A;
	b = B;
	ll ret;
	vi w(m,0);
	ret = ask(w);
	base = ret;
	len = ret/A;
	if(s3){
		pii ans = search(0, m-1);
		answer(ans.first, ans.second + 1);
	}
	else{
		vi dep(N);
		dep[0] = 0;
		queue<int>q;
		q.push(0);
		vb vis(N);
		vis[0] = 1;
		vpii adj[N];
		f0r(i, m){
			adj[U[i]].pb({V[i], i});
			adj[V[i]].pb({U[i], i});
		}
		vi par(N, -1);
		while(!q.empty()){
			int cur = q.front();
			q.pop();
			for(auto u : adj[cur]){
				if(vis[u.first])continue;
				par[u.first] = u.second;
				vis[u.first] = 1;
				dep[u.first] = dep[cur] + 1;
				q.push(u.first);
			}
		}
		//vout(par);
		
		vi poss;
		f0r(i, N){
			if(dep[i] == len)poss.pb(i);
		}
		//vout(poss);
		
		int l = 0;
		int r = poss.size() - 1;
		while(l < r){
			vi w(m, 0);
			int mid = (l + r)/2;
			//set l to mid
			for(int i = l; i<=mid; i++){
				w[par[poss[i]]] = 1;
			}
			ret = ask(w);
			if(ret > base){
				r = mid;
			}
			else{
				l = mid + 1;
			}
		}
	  	answer(0, poss[l]);
	}
	
  	
}

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