Submission #138830

#	Time	Username	Problem	Language	Result	Execution time	Memory
138830		muradeyn	Highway Tolls (IOI18_highway)	C++14	5 / 100	371 ms	19192 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define intt long long 

using namespace std;

const int maxx = 100000;

map< pair<int,int> , int>mp;

vector<int>v[maxx];

vector<int>w;

vector< pair<int,int> >cur;

int x , y;

void dfs(int s,int p,int d,int need) {
	if (d == need) {
		cur.push_back({p , s});
		return;
	}
	for (int to : v[s]) {
		if (to == p)continue;
		dfs(to , s , d + 1 , need);
	}
}

void find_pair(int n, vector<int> u, vector<int> vv, int a, int b) {
	int m = u.size();
	for (int i = 0;i<m;i++) {
		x = u[i];
		y = vv[i];
		mp[{x , y}] = mp[{y , x}] = i;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	w.resize(m , 0);
	int ret = ask(w);
	int dist = ret / a;
	dfs(0 , 0 , 0 , dist);
	while (cur.size() > 1) {
		vector< pair<int,int> >lft;
		vector< pair<int,int> >rgt;
		intt lw = dist * a;
		for (int i = 0;i<cur.size() / 2;i++) {
			w[mp[{cur[i].F , cur[i].S}]] = 0;
			lft.push_back(cur[i]);
		}
		for (int i = cur.size() / 2;i<cur.size();i++) {
			w[mp[{cur[i].F , cur[i].S}]] = 1;
			rgt.push_back(cur[i]);
		}
		ret = ask(w);
		if (ret == lw)cur = lft;
		else cur = rgt;
	}
	answer(0 , cur.back().S);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i<cur.size() / 2;i++) {
                  ~^~~~~~~~~~~~~~~
highway.cpp:53:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = cur.size() / 2;i<cur.size();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