Submission #399174

#	Time	Username	Problem	Language	Result	Execution time	Memory
399174		kshitij_sodani	Highway Tolls (IOI18_highway)	C++14	100 / 100	465 ms	22496 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<llo> adj2[100001];

vector<pair<llo,llo>> lev[100001];
llo dist[100001];
llo ba[100001];
llo vis[100001];
llo vis2[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 dfs2(int no){
	vis2[no]=1;
	for(auto  j:adj2[no]){
		if(vis2[j]==0){
			dfs2(j);
		}
	}
}
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});
	}
	llo low=0;
	for(int j=19;j>=0;j--){
		if(low+(1LL<<j)<=m){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				cur2[i]=1;
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	for(int i=0;i<low;i++){
		//if((aa==1 and bb==2)){
			cur[i]=1;
		//}
	}

	//return;
	pair<int,int> no={uu[low],vv[low]};
	for(int i=0;i<n;i++){
		dist[i]=-1;
		ba[i]=-1;
	}
	queue<int> ss;
	ss.push(no.a);
	dist[no.a]=0;
	while(ss.size()){
		int cot=ss.front();
		ss.pop();
		for(auto j:adj[cot]){
			if(j.b<low){
				continue;
			}
			if(dist[j.a]==-1){

				dist[j.a]=dist[cot]+1;
				ba[j.a]=cot;
				ss.push(j.a);
			}
		}
	}
	vector<pair<int,int>> tt;
	for(int i=0;i<n;i++){
		if(dist[i]==-1){
			vis2[i]=2;
		}
	}
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			if(dist[i]==-1 or dist[j.a]==-1){
				continue;
			}

			if(dist[j.a]==dist[i]-1 and dist[j.a]>0){
				adj2[j.a].pb(i);
			}
		}
	}
	dfs2(no.b);
	for(int i=0;i<n;i++){
		if(vis2[i]==0){
			tt.pb({dist[i],i});
		}
	}
	/*cout<<no.a<<"::"<<no.b<<endl;
	for(int i=0;i<n;i++){
		cout<<vis2[i]<<":";
	}
	cout<<endl;*/
	sort(tt.begin(),tt.end());
	reverse(tt.begin(),tt.end());
	low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=tt.size()){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				int x=tt[i].b;
				for(auto k:adj[x]){
					if(dist[k.a]==dist[x]-1 and dist[k.a]!=-1){
						cur2[k.b]=1;
					}
				}
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	//cout<<low<<"::"<<endl;

	int xx=no.a;
	if(low<tt.size()){
		xx=tt[low].b;
	}
	tt.clear();
	for(int i=0;i<n;i++){
		if(vis2[i]==1){
			tt.pb({dist[i],i});
		}
	}
	sort(tt.begin(),tt.end());
	reverse(tt.begin(),tt.end());
	low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=tt.size()){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				int x=tt[i].b;
				for(auto k:adj[x]){
					if(dist[k.a]==dist[x]-1 and dist[k.a]!=-1){
						cur2[k.b]=1;
					}
				}
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	//cout<<low<<"::"<<endl;


/*	llo zz=xx;
	while(zz>=0){
		vis[zz]=1;
		zz=ba[zz];
	}
	low=0;

	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=n){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				if(vis[tt[i].b]==1){
				//	cout<<tt[i].b<<"???"<<endl;
					continue;
				}

				int x=tt[i].b;
				for(auto k:adj[x]){

					if(dist[k.a]==dist[x]-1){
						cur2[k.b]=1;

					}
				}
			}
			if(ask(cur2)==ans){

				low+=(1<<j);
			}
		}
	}*/


//	cout<<low<<endl;
	//cout<<tt[low].b<<",,"<<endl;
	/*if(low==tt.size()){
		answer(xx,no.a);
		return;
	}*/
	answer(xx,tt[low].b);





/*	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:123:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   if(low+(1<<j)<=tt.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~
highway.cpp:141:8: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  if(low<tt.size()){
      |     ~~~^~~~~~~~~~
highway.cpp:154:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   if(low+(1<<j)<=tt.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~

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