Submission #139929

#	Time	Username	Problem	Language	Result	Execution time	Memory
139929		almogwald	Highway Tolls (IOI18_highway)	C++14	51 / 100	618 ms	262148 KiB

highway

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include "highway.h"
//#include "doll.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define fort(i,m,n) for(int i=m;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	int m = U.size();
	veci w(m);
	lol toll = ask(w);
	vector<vector<point>> cons(n);
	fori(i,m){
		cons[U[i]].push_back({V[i],i});
		cons[V[i]].push_back({U[i],i});
	}
	veci ord;
	vector<point>x;
	x.push_back({0,-1});
	veci p(n);
	while(!x.empty()){
		int cur=x.back().first;
		int pp=x.back().second;
		x.pop_back();
		p[cur]=pp;
		ord.push_back(pp);
		fori(i,cons[cur].size()){
			if(cons[cur][i].second!=pp){
				x.push_back(cons[cur][i]);
			}
		}
	}
	int l=1,h=m;
	while(l<h){
		int mid=(l+h+1)/2;
		fori(i,m){
			w[i]=0;
		}
		fort(i,mid,h+1){
			w[ord[i]]=1;
		}
		lol tol = ask(w);
		if(tol==toll){
			h=mid-1;
		}else{
			l=mid;
		}
	}
	l=ord[l];
	int s=0;
	fori(i,n){
		if(p[i]==l){
			s=i;
			break;
		}
	}
	ord.resize(0);

	x.push_back({s,-1});

	while(!x.empty()){
		int cur=x.back().first;
		int pp=x.back().second;
		x.pop_back();
		p[cur]=pp;
		ord.push_back(pp);
		fori(i,cons[cur].size()){
			if(cons[cur][i].second!=pp){
				x.push_back(cons[cur][i]);
			}
		}
	}
	l=1,h=m;
	while(l<h){
		int mid=(l+h+1)/2;
		fori(i,m){
			w[i]=0;
		}
		fort(i,mid,h+1){
			w[ord[i]]=1;
		}
		lol tol = ask(w);
		if(tol==toll){
			h=mid-1;
		}else{
			l=mid;
		}
	}
	l=ord[l];
	int t=0;
	fori(i,n){
		if(p[i]==l){
			t=i;
			break;
		}
	}
	answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
highway.cpp:41:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
highway.cpp:41:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~
highway.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
highway.cpp:81:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
highway.cpp:81:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~

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