Submission #349509

#	Time	Username	Problem	Language	Result	Execution time	Memory
349509		tengiz05	Highway Tolls (IOI18_highway)	C++17	Compilation error	0 ms	0 KiB

highway

#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
typedef long long ll;
const int _N = 90005;
vector<int> edges[_N];
vector<pii> edge[_N];
vector<pii> EDGES;
int n, m, a, b;
ll dist;
pii num(ll x){
	ll dif = x-dist;
	assert(dif%(b-a)==0);
	return {dist - dif/(b-a),dif/(b-a)};
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	a=A,b=B;
	for(int i=0;i<M;i++){
		edges[U[i]].pb(V[i]);
		edges[V[i]].pb(U[i]);
		edge[U[i]].pb({V[i],i});
		edge[V[i]].pb({U[i],i});
		EDGES.pb({U[i],V[i]});
	}
	vector<int> toask(m,0);
	ll TMP = ask(toask);
	dist = TMP/a;
	int l=0,r=m-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[i] = 1;
		for(int i=mid+1;i<m;i++)toask[i] = 0;
		auto [x, y] = num(ask(toask));
		if(y == 0)l = mid+1;
		else r = mid;
	}
	int root = EDGES[l].first;
	//~ cout << l << '-' << r << '\n';
	//~ cout << root << '\n';
	queue<int> q;
	vector<bool> used(n,0);
	q.push(root);used[root] = true;
	vector<int> v;
	vector<pii> vse;
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto [to, ind] : edge[u]){
			if(used[to])continue;
			used[to] = true;
			vse.pb({u, to});
			v.pb(ind);
			q.push(to);
		}
	}
	l=0,r=v.size()-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[v[i]] = 0;
		for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
		auto [x, y] = num(ask(toask));
		if(y != 0)l = mid+1;
		else r = mid;
	}
	//~ cout << l << '-' << r << '\n';
	//~ cout << EDGES[v[l]].first << ' ' << EDGES[v[l]].second << '\n';
	//~ for(auto [x, y] : vse){
		//~ cout << x << ';' << y << '\n';
	//~ }
	int s = vse[l].second;
	root = s;
	used.assign(n,0);
	q.push(root);used[root] = true;
	v.clear();
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto [to, ind] : edge[u]){
			if(used[to])continue;
			used[to] = true;
			vse.pb({u, to});
			v.pb(ind);
			q.push(to);
		}
	}
	l=0,r=v.size()-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[v[i]] = 0;
		for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
		auto [x, y] = num(ask(toask));
		if(y != 0)l = mid+1;
		else r = mid;
	}
	int t = vse[l].first;
	//~ cout << s << ' ' << t << '\n';
	answer(s,t);
	
	return;
}


/*


7 6
1 2
3 4
0 2
0 3
3 4
2 6
2 5
2 1


*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:25:16: error: 'M' was not declared in this scope
   25 |  for(int i=0;i<M;i++){
      |                ^