Submission #169883

#	Time	Username	Problem	Language	Result	Execution time	Memory
169883		dennisstar	Highway Tolls (IOI18_highway)	C++11	100 / 100	373 ms	10308 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

vim G[90010];
int chk[90010];

void find_pair(int N, vim U, vim V, int A, int B) {
	int M=U.size();
	vim w(M);
	ll L=ask(w);

	for (int i=0; i<M; i++) G[U[i]].push_back(V[i]), G[V[i]].push_back(U[i]);

	int s, e;
	for (s=0, e=M-1; s<e; ) {
		int m=(s+e)/2;
		fill(w.begin(), w.begin()+m+1, 1);
		fill(w.begin()+m+1, w.end(), 0);
		if (L!=ask(w)) e=m;
		else s=m+1;
	}

	vector<pii> stk; vector<int> ar[2];
	stk.push_back({0, U[s]}); stk.push_back({1, V[s]});
	chk[U[s]]=chk[V[s]]=1;
	for (int i=0; i<stk.size(); i++) {
		ar[stk[i].fi].push_back(stk[i].se);
		for (int j:G[stk[i].se]) {
			if (chk[j]) continue;
			chk[j]=1;
			stk.push_back({stk[i].fi, j});
		}
	}

	int S, T;
	for (s=0, e=ar[0].size()-1; s<e; ) {
		int m=(s+e+1)/2;
		vim X(N);
		fill(w.begin(), w.end(), 0);
		for (int i=m; i<ar[0].size(); i++) X[ar[0][i]]=1;
		for (int i=0; i<M; i++) {
			if (X[U[i]]!=X[V[i]]) w[i]=1;
		}
		if (L!=ask(w)) s=m;
		else e=m-1;
	}
	S=ar[0][s];

	for (s=0, e=ar[1].size()-1; s<e; ) {
		int m=(s+e+1)/2;
		vim X(N);
		fill(w.begin(), w.end(), 0);
		for (int i=m; i<ar[1].size(); i++) X[ar[1][i]]=1;
		for (int i=0; i<M; i++) {
			if (X[U[i]]!=X[V[i]]) w[i]=1;
		}
		if (L!=ask(w)) s=m;
		else e=m-1;
	}
	T=ar[1][s];

	answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vim, vim, int, int)':
highway.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<stk.size(); i++) {
                ~^~~~~~~~~~~
highway.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=m; i<ar[0].size(); i++) X[ar[0][i]]=1;
                 ~^~~~~~~~~~~~~
highway.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=m; i<ar[1].size(); i++) X[ar[1][i]]=1;
                 ~^~~~~~~~~~~~~

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