Submission #114920

#	Time	Username	Problem	Language	Result	Execution time	Memory
114920		tutis	Highway Tolls (IOI18_highway)	C++17	40 / 100	252 ms	10456 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
	vector<int>adj[N];
	int M = U.size();
	for (int i = 0; i < M; i++)
	{
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	vector<int>tarp;
	for (int i = 0; i < M; i++)
		tarp.push_back(i);
	vector<int>w(M, 1);
	ll maxi = ask(w);
	while (tarp.size() > 1)
	{
		vector<int>t1;
		vector<int>t2;
		for (int i = 0; i < tarp.size(); i++)
		{
			if (i < tarp.size() / 2)
				t1.push_back(tarp[i]);
			else
				t2.push_back(tarp[i]);
		}
		fill_n(w.begin(), M, 1);
		for (int i : t1)
			w[i] = 0;
		if (ask(w) < maxi)
			tarp = t1;
		else
			tarp = t2;
	}
	assert(tarp.size() == 1);
	int u[2] = {U[tarp[0]], V[tarp[0]]};
	int d[2][N];
	int pa[2][N];
	for (int t : {0, 1})
	{
		fill_n(d[t], N, N + 3);
		d[t][u[t]] = 0;
		queue<int>Q;
		Q.push(u[t]);
		while (!Q.empty())
		{
			int a = Q.front();
			Q.pop();
			for (int b : adj[a])
			{
				if (d[t][b] > d[t][a] + 1)
				{
					d[t][b] = d[t][a] + 1;
					Q.push(b);
				}
			}
		}
		for (int i = 0; i < M; i++)
		{
			if (d[t][U[i]] < d[t][V[i]])
				pa[t][V[i]] = i;
			if (d[t][U[i]] > d[t][V[i]])
				pa[t][U[i]] = i;
		}
		pa[t][u[t]] = u[t];
	}
	ll d_st = maxi / ll(B);
	vector<int>v[2];
	for (int t : {0, 1})
	{
		for (int i = 0; i < N; i++)
		{
			if (d[t][i] < d[1 - t][i])
				v[t].push_back(i);
		}
	}
	fill_n(w.begin(), M, 1);
	if (v[0].size() > 1)
		for (int i : v[0])
			w[pa[0][i]] = 0;
	int d_s = ((maxi - ask(w)) / ll(B - A));
	int d_t = d_st - d_s - 1;
	vector<int>s, t;
	for (int i : v[0])
		if (d[0][i] == d_s)
			s.push_back(i);
	for (int i : v[1])
		if (d[1][i] == d_t)
			t.push_back(i);
	while (s.size() > 1)
	{
		vector<int>s1, s2;
		for (int i = 0; i < s.size(); i++)
		{
			if (i < s.size() / 2)
				s1.push_back(s[i]);
			else
				s2.push_back(s[i]);
		}
		fill_n(w.begin(), M, 1ll);
		for (int i : s1)
			w[pa[0][i]] = 0;
		if (ask(w) < maxi)
			s = s1;
		else
			s = s2;
	}
	while (t.size() > 1)
	{
		vector<int>t1, t2;
		for (int i = 0; i < t.size(); i++)
		{
			if (i < t.size() / 2)
				t1.push_back(t[i]);
			else
				t2.push_back(t[i]);
		}
		fill_n(w.begin(), M, 1ll);
		for (int i : t1)
			w[pa[1][i]] = 0;
		if (ask(w) < maxi)
			t = t1;
		else
			t = t2;
	}
	answer(s[0], t[0]);
}/*
int main()
{

}
/**/

Compilation message (stderr)

highway.cpp:135:1: warning: "/*" within comment [-Wcomment]
 /**/
  
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tarp.size(); i++)
                   ~~^~~~~~~~~~~~~
highway.cpp:25:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < tarp.size() / 2)
        ~~^~~~~~~~~~~~~~~~~
highway.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~
highway.cpp:98:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < s.size() / 2)
        ~~^~~~~~~~~~~~~~
highway.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < t.size(); i++)
                   ~~^~~~~~~~~~
highway.cpp:116:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < t.size() / 2)
        ~~^~~~~~~~~~~~~~

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