Submission #398691

#	Time	Username	Problem	Language	Result	Execution time	Memory
398691		kshitij_sodani	Highway Tolls (IOI18_highway)	C++14	51 / 100	198 ms	36552 KiB

highway

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "highway.h"

vector<int> cur;
vector<pair<llo,llo>> adj[100001];
vector<pair<llo,llo>> lev[100001];
void dfs(llo no,llo par=-1,llo levv=0,llo la=-1){
	lev[levv].pb({no,la});
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no,levv+1,j.b);
		}
	}
}
void find_pair(int n, std::vector<int> uu, std::vector<int> vv, int aa, int bb) {
	int m=uu.size();
	for(int i=0;i<m;i++){
		cur.pb(0);
	}
	llo ans=ask(cur);
	for(int i=0;i<m;i++){
		adj[uu[i]].pb({vv[i],i});
		adj[vv[i]].pb({uu[i],i});
	}
	int l=0;
	int r=m-1;
	while(l<r){
		int mid=(l+r)/2;
		vector<int> cur2=cur;
		for(int i=l;i<=mid;i++){
			cur2[i]=1;
		}
		if(ask(cur2)==ans){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	//return;
	pair<int,int> no={uu[l],vv[l]};
	for(int i=0;i<=n;i++){
		lev[i].clear();
	}
	dfs(no.a,no.b,0,l);
	vector<pair<llo,llo>> ord;
	for(int i=n;i>=0;i--){
		for(auto j:lev[i]){
			ord.pb(j);
		}
	}
	llo low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=ord.size()){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				cur2[ord[i].b]=1;
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	int xx=ord[low].a;
	ord.clear();
	for(int i=0;i<=n;i++){
		lev[i].clear();
	}
	dfs(no.b,no.a,0,l);
	for(int i=n;i>=0;i--){
		for(auto j:lev[i]){
			ord.pb(j);
		}
	}
	low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=ord.size()){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				cur2[ord[i].b]=1;
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	int yy=ord[low].a;
	answer(xx,yy);



}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:63:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if(low+(1<<j)<=ord.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~~
highway.cpp:86:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   if(low+(1<<j)<=ord.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~~

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