Submission #566674

#	Time	Username	Problem	Language	Result	Execution time	Memory
566674		PiejanVDC	Highway Tolls (IOI18_highway)	C++17	18 / 100	339 ms	32736 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

vector<int>adj[(int)9e4+5];

long long ask(const vector<int>&v);
void answer(int s, int t);

void find_pair(int n, vector<int> U, vector<int> V, int a, int b) {
	int m = (int)U.size();
	vector<int>AA(m,0);
	long long ans = ask(AA);
	long long dist = ans / a;
	int l = 0, r = m-1;
	int id;
	while(l <= r) {
		if(l == r) {
			id = l;
			break;
		}
		int mid = (l+r)/2;
		vector<int>A(m,0);
		for(int i = 0 ; i <= mid ; i++)
			A[i] = 1;
		if(ask(A) != ans) {
			id = mid;
			r = mid;
		} else {
			l = mid+1;
		}
	}

	int f = U[id], s = V[id];
	//cout << f << " " << s << "\n";
	map<pair<int,int>,int>mp;
	for(int i = 0 ; i < m ; i++) if(i != id)
		adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]), mp[{U[i],V[i]}] = mp[{V[i],U[i]}] = i;

	// now binary search each part

	vector<vector<int>>d(n);
	vector<vector<int>>h(n);
	d[0].push_back(f);
	h[0].push_back(id);
	queue<int>q;

	q.push(f);
	vector<bool>vis(n,0);
	vis[f] = 1;
	int D = 0;
	while(!q.empty()) {
		int sz = q.size();
		while(sz--) {
			int node = q.front();
			q.pop();
			vis[node] = 1;
			for(auto z : adj[node]) {
				if(!vis[z])
					q.push(z), d[D+1].push_back(z), h[D+1].push_back(mp[{node,z}]);
			}
		}
		D++;
	}

	l = 0, r = dist;
	int P = 0;

	while(l <= r) {
		int mid = (l+r)/2;
		vector<int>B(m,0);

		if(h[mid].empty()) {
			r = mid-1;
			continue;
		}

		for(int i = 0 ; i < h[mid].size() ; i++)
			B[h[mid][i]] = 1;

		if(ask(B) != ans)
			P = mid, l = mid+1;
		else
			r = mid-1;
	}

	dist -= P;
	dist++;

	l = 0, r = d[P].size();
	int LE = f;
	while(l <= r) {
		if(l == r) {
			LE = d[P][l];
			break;
		}

		int mid = (l+r)/2;
		vector<int>B(m,0);

		for(int i = 0 ; i <= mid ; i++)
			B[h[P][i]] = 1;

		if(ask(B) != ans)
			LE = d[P][mid], r = mid;
		else
			l = mid+1;

	}

	////////////////////////////////

	vector<vector<int>>d2(n);
	vector<vector<int>>h2(n);
	d2[0].push_back(s);
	h2[0].push_back(id);

	q.push(s);
	vector<bool>vis2(n,0);
	vis2[f] = 1;
	D = 0;
	while(!q.empty()) {
		int sz = q.size();
		while(sz--) {
			int node = q.front();
			q.pop();
			vis2[node] = 1;
			for(auto z : adj[node]) {
				if(!vis2[z])
					q.push(z), d2[D+1].push_back(z), h2[D+1].push_back(mp[{node,z}]);
			}
		}
		D++;
	}

	l = 0, r = dist;
	P = 0;

	while(l <= r) {
		int mid = (l+r)/2;
		vector<int>B(m,0);

		if(h2[mid].empty()) {
			r = mid-1;
			continue;
		}

		for(int i = 0 ; i < h2[mid].size() ; i++)
			B[h2[mid][i]] = 1;

		if(ask(B) != ans)
			P = mid, l = mid+1;
		else
			r = mid-1;
	}

	l = 0, r = d2[P].size();
	int RE = s;
	while(l <= r) {
		if(l == r) {
			RE = d2[P][l];
			break;
		}

		int mid = (l+r)/2;
		vector<int>B(m,0);

		for(int i = 0 ; i <= mid ; i++)
			B[h2[P][i]] = 1;

		if(ask(B) != ans)
			RE = d2[P][mid], r = mid;
		else
			l = mid+1;

	}		

	//cout << LE << " " << RE << "\n";
	answer(LE, RE);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i = 0 ; i < h[mid].size() ; i++)
      |                   ~~^~~~~~~~~~~~~~~
highway.cpp:148:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for(int i = 0 ; i < h2[mid].size() ; i++)
      |                   ~~^~~~~~~~~~~~~~~~

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