Submission #334077

#	Time	Username	Problem	Language	Result	Execution time	Memory
334077		nicholask	Highway Tolls (IOI18_highway)	C++14	5 / 100	168 ms	8448 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
vector <pair <int,int> > g[90000]; //first: connection to which node, second: edge no.
int dist;
vector <pair <int,int> > poss;
void dfs(int cur,int prev,int d){
	for (auto&i:g[cur]){
		if (i.x==prev) continue;
		if (d+1==dist) poss.push_back({i.y,i.x});
		else dfs(i.x,cur,d+1);
	}
}
void find_pair(int n,vector <int> u,vector <int> v,int a,int b){
	int m=u.size();
	for (int i=0; i<m; i++){
		g[u[i]].push_back({v[i],i});
		g[v[i]].push_back({u[i],i});
	}
	vector <int> query(m,0);
	dist=ask(query)/a;
	bool can=1;
	for (int i=0; i<m; i++){
		if (u[i]!=i||v[i]!=i+1){
			can=0;
			break;
		}
	}
	if (can){ //subtask 3
		vector <int> possible;
		for (int i=0; i<n; i++) possible.push_back(i);
		while (possible.size()>1){
			vector <int> f,s;
			for (int i=0; i<possible.size(); i++){
				if (i<(possible.size()/2)) f.push_back(possible[i]);
				else s.push_back(possible[i]);
			}
			vector <int> query(m,0);
			for (auto&i:f) query[i]=1;
			if (ask(query)==a*dist) possible=s;
			else possible=f;
		}
		answer(possible[0],possible[0]+dist);
	} else {
		dfs(0,-1,0);
		while (poss.size()>1){
			vector <pair <int,int> > f,s;
			for (int i=0; i<poss.size(); i++){
				if (i<(poss.size()/2)) f.push_back(poss[i]);
				else s.push_back(poss[i]);
			}
			vector <int> query(m,0);
			for (auto&i:f) query[i.x]=1;
			if (ask(query)==a*dist) poss=s;
			else poss=f;
		}
		answer(0,poss[0].y);
	}
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for (int i=0; i<possible.size(); i++){
      |                  ~^~~~~~~~~~~~~~~~
highway.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if (i<(possible.size()/2)) f.push_back(possible[i]);
      |         ~^~~~~~~~~~~~~~~~~~~~
highway.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for (int i=0; i<poss.size(); i++){
      |                  ~^~~~~~~~~~~~
highway.cpp:51:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if (i<(poss.size()/2)) f.push_back(poss[i]);
      |         ~^~~~~~~~~~~~~~~~

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