Submission #158162

#	Time	Username	Problem	Language	Result	Execution time	Memory
158162		kig9981	Highway Tolls (IOI18_highway)	C++17	51 / 100	238 ms	14292 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[90000];
set<int> gv[90000];
int g[90000];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	int M=U.size(), sg=0, tg=1, gnum=1;
	vector<int> W(M);
	long long dist=ask(W);
	for(int b=1;;b<<=1) {
		for(int i=0;i<M;i++) W[i]=(U[i]^V[i])&b ? 1:0;
		if((ask(W)-dist)/(B-A)&1) {
			for(int i=0;i<N;i++) gv[g[i]=(i&b) ? 1:0].insert(i);
			break;
		}
	}
	while(gv[sg].size()>1) {
		++gnum;
		for(auto c: gv[sg]) {
			gv[gnum].insert(c);
			g[c]=gnum;
			if(2*gv[gnum].size()>=gv[sg].size()) break;
		}
		for(auto c: gv[gnum]) gv[sg].erase(c);
		for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
		if((ask(W)-dist)/(B-A)&1) sg=gnum;
	}
	while(gv[tg].size()>1) {
		++gnum;
		for(auto c: gv[tg]) {
			gv[gnum].insert(c);
			g[c]=gnum;
			if(2*gv[gnum].size()>=gv[tg].size()) break;
		}
		for(auto c: gv[gnum]) gv[tg].erase(c);
		for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
		if((ask(W)-dist)/(B-A)&1) tg=gnum;
	}
	answer(*gv[sg].begin(),*gv[tg].begin());
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:30:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
                             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
highway.cpp:41:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
                             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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