Submission #125505

#	Time	Username	Problem	Language	Result	Execution time	Memory
125505		TuGSGeReL	통행료 (IOI18_highway)	C++17	51 / 100	373 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
 
ll mn;
int m, a, b, par[90000], num[90000];
vector <pii> edg[90000];
vector <int> check, arr;
 
void dfs(int u, int pr)
{
	arr.pub(u);
	
	for (auto x : edg[u])
	{
		if ( x.ff != pr )
		{
			par[x.ff] = u;
			num[x.ff] = x.ss;
			dfs(x.ff, u);
		}
	}
}
 
bool shal(int k, int p)
{
	for (int i = k; i <= p; i++)
		check[num[arr[i]]] = 0;
	
	if ( ask(check) > mn )
		return 1;
	
	return 0;
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	for (int i = 0; i < U.size(); i++)
	{
		edg[U[i]].pub(mp(V[i], i));
		edg[V[i]].pub(mp(U[i], i));
	}
	
	m = U.size();
	
	for (int i = 0; i < m; i++)
		check.pub(0);
	
	dfs(0, -1);
	mn = ask(check);
	int l = 1, r = arr.size() - 1;

	for (int i = 0; i < m; i++)
		check[i] = 1;
	
	while (l != r)
	{
		int mid = (l + r) / 2;
		
		if ( shal(l, mid) )
			l = mid + 1;
		
		else
		{
			r = mid;
			
			for ( int i = l; i <= mid; i++)
				check[num[arr[i]]] = 1;
		}
	}
	
	a = arr[l];
	arr.clear();
	dfs(a, -1);
	l = 1, r = arr.size() - 1;
	
	for (int i = 0; i < m; i++)
		check[i] = 1;
	
	while (l != r)
	{
		int mid = (l + r) / 2;
		
		if ( shal(l, mid) )
			l = mid + 1;
		
		else
		{
			r = mid;
			
			for ( int i = l; i <= mid; i++)
				check[num[arr[i]]] = 1;
		}
	}
	
	b = arr[l];
	answer(a, b);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++)
                  ~~^~~~~~~~~~

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