Submission #348652

#	Time	Username	Problem	Language	Result	Execution time	Memory
348652		juggernaut	Highway Tolls (IOI18_highway)	C++14	51 / 100	660 ms	13580 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector<int> Q;
ll Cost = 0;
int p[maxn], par[maxn];
vector<pair<int,int>> g[maxn];
bool mark[maxn];
 
int Que[maxn], head = 0, tail = 0, h[maxn];
int n;
 
int Get(int v){
	memset(h, -1, sizeof h);
	tail = head = 0;
	h[v] = 0, Que[head++] = v;
	while (tail < head){
		int v = Que[tail++];
		for (auto [u,idx] : g[v])
			if (h[u] == -1)
				h[u] = h[v]+1, Que[head++] = u;
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	sort(p, p+n, [](int A, int B){
		return h[A] > h[B];
	});
	int L = -1, R = n-1;
	while (R-L > 1){
		int mid = (L+R) >> 1;
		for (int i = 0; i <= mid; i++){
			int v = p[i];
			for (auto [u,idx] : g[v])
				Q[idx] |= 1;
		}
		ll nowCost = ask(Q);
		for (int i = 0; i <= mid; i++){
			int v = p[i];
			for (auto [u,idx] : g[v])
				Q[idx] &= 0;
		}
		if (nowCost == Cost)
			L = mid;
		else
			R = mid;
	}
	return p[R];
}
 
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	::n = n;
	int m = U.size();
	Q.resize(m);
	for (int i = 0; i < m; i++){
		Q[i] = 0;
		g[V[i]].push_back({U[i],i});
		g[U[i]].push_back({V[i],i});
	}
	Cost = ask(Q);
	int S = Get(0);
	int T = Get(S);
	answer(S,T);
}

Compilation message (stderr)

highway.cpp: In function 'int Get(int)':
highway.cpp:21:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |   for (auto [u,idx] : g[v])
      |             ^
highway.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |    for (auto [u,idx] : g[v])
      |              ^
highway.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |    for (auto [u,idx] : g[v])
      |              ^

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