Submission #831915

#	Time	Username	Problem	Language	Result	Execution time	Memory
831915		Antekb	Highway Tolls (IOI18_highway)	C++17	100 / 100	210 ms	28064 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii > vii;

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

const int N=2e5;
vii E[N], E2[N];
int dep[N], par[N];
vii edg;
vii pre[2];
void dfs(int v, int num){
	for(pii ee:E2[v]){
		int u=ee.st;
		if(u!=par[v]){
			pre[num].pb(ee);
			par[u]=v;
			dfs(u, num);
		}
	}
}
void find_pair(int n, std::vector<int> UU, std::vector<int> VV, int A, int B) {
	int M = UU.size();
	for(int i=0; i<M; i++){
		edg.eb(UU[i],VV[i]);
		E[UU[i]].eb(VV[i], i);
		E[VV[i]].eb(UU[i], i );
	}
	vi w(M);
	int dist=ask(w)/A;
	int l=0, r=M;
	while(l<r){
		int m=(l+r)/2;
		w.clear();
		w.resize(m+1, 0);
		w.resize(M, 1);
		if(ask(w)==dist*1ll*A)r=m;
		else l=m+1;
	}
	int root=l;
	vi V;
	V.pb(edg[root].st);
	V.pb(edg[root].nd);
	dep[V[0]]=dep[V[1]]=1;
	vi drz={root};
	for(int i=0; i<V.size(); i++){
		int v=V[i];
		for(pii ee:E[v]){
			if(dep[ee.st]==0){
				dep[ee.st]=dep[v]+1;
				V.pb(ee.st);
				E2[v].pb(ee);
				drz.pb(ee.nd);
			}
		}
	}
	deb(root, dist);
	par[V[0]]=V[1];
	par[V[1]]=V[0];
	dfs(V[0], 0);
	dfs(V[1], 1);
	int res[2];
	for(int ii=0; ii<2; ii++){
		int l=0, r=pre[ii].size();
		for(auto ee:pre[ii]){
			//deb(ee.st, ee.nd);
		}
		while(l<r){
			int m=(l+r)>>1;
			w.resize(0);
			w.resize(M, 1);
			w[root]=0;
			for(auto ee:pre[ii^1])w[ee.nd]=0;
			for(int i=0; i<m; i++)w[pre[ii][i].nd]=0;
			//deb(m);
			//for(int i:w){cerr<<i<<" ";}cerr<<"\n";
			//deb(ask(w));
			if(ask(w)==A*1ll*dist){
				r=m;
			}
			else{
				l=m+1;
			}
		}
		if(l==0)res[ii]=V[ii];
		else res[ii]=pre[ii][l-1].st;
		deb(l, res[ii]);
	}
	answer(res[0], res[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
highway.cpp:80:12: warning: variable 'ee' set but not used [-Wunused-but-set-variable]
   80 |   for(auto ee:pre[ii]){
      |            ^~

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