Submission #621041

#	Time	Username	Problem	Language	Result	Execution time	Memory
621041		MeGustaElArroz23	Highway Tolls (IOI18_highway)	C++14	51 / 100	163 ms	23024 KiB

highway

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

using namespace std;

#define ll long long
//#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define vvii vector<vii>
#define vb vector<bool>

#define fi first
#define se second
#define pb push_back

#define piii pair<pii,int>
#define viii vector<piii>

int n;
int m;
ll a;
ll b;
ll dist;

vi u;
vi v;

int myask(vi h){
	vi toask(m,0);
	for (int x:h) toask[x]=1;
	ll ans=ask(toask);
	ans-=a*dist;
	return ans/(b-a);
}

vector<vector<piii>> withprof;

vvii conexiones;

void dfs1(int ac, int ant, int prof){
	for (pii y:conexiones[ac]){
		if (y.fi!=ant){
			withprof[prof].pb(piii{pii{ac,y.fi},y.se}); //up down id
			dfs1(y.fi,ac,prof+1);
		}
	}
}

vii sussy;

void dfs2(int ac, int ant, int acdis){
	for (pii y:conexiones[ac]){
		if (y.fi!=ant){
			if (acdis==dist-1) sussy.pb(y);
			dfs2(y.fi,ac,acdis+1);
		}
	}
}

void find_pair(int N, vi U, vi V, int A, int B) {
	n=N; m=U.size(); a=A; b=B; u=U; v=V;
	dist=ask(vi(m,0))/a;

	//cerr << "A";
	conexiones=vvii(n);
	for (int i=0;i<m;i++){
		conexiones[u[i]].pb(pii{v[i],i});
		conexiones[v[i]].pb(pii{u[i],i});
	}
	//cerr << "A";

	withprof=vector<vector<piii>>(n);

	//cerr << "A";
	dfs1(0,-1,0);
	//cerr << "A";

	int l=0;
	int r=n;
	while (l!=r-1){
		int mid=(l+r)/2;
		vi toadd;
		for (int prof=mid;prof<n-1;prof++){
			for (piii x:withprof[prof]) toadd.pb(x.se);
		}
		if (myask(toadd)>0) l=mid;
		else r=mid;
	}

	//cerr << "A";

	viii sus=withprof[l];

	while (sus.size()>1){
		viii sus1;
		viii sus2;
		for (int i=0;i<sus.size();i++){
			if (i%2) sus1.pb(sus[i]);
			else sus2.pb(sus[i]);
		}
		vi toadd;
		for (piii x:sus1) toadd.pb(x.se);
		if (myask(toadd)) sus=sus1;
		else sus=sus2;
	}

	//cerr << "A";

	int sol1=sus[0].fi.se;

	dfs2(sol1,-1,0);

	//cerr << "A";

	while (sussy.size()>1){
		vii sussy1;
		vii sussy2;
		for (int i=0;i<sussy.size();i++){
			if (i%2) sussy1.pb(sussy[i]);
			else sussy2.pb(sussy[i]);
		}
		vi toadd;
		for (pii x:sussy1) toadd.pb(x.se);
		if (myask(toadd)) sussy=sussy1;
		else sussy=sussy2;
	}

	//cerr << "A";

	int sol2=sussy[0].fi;

	answer(sol1,sol2);

}

// N M A B S T
// U[i] V[i]

/* 
4 3 1 3 1 3
0 1 
 
0 3 
1 2
*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (int i=0;i<sus.size();i++){
      |                ~^~~~~~~~~~~
highway.cpp:121:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int i=0;i<sussy.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