제출 #399118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399118		kshitij_sodani	통행료 (IOI18_highway)	C++14	100 / 100	678 ms	17848 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];
llo dist[100001];
llo ba[100001];
llo vis[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});
	}
	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 and (aa==1 and bb==2)){
				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++){
		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)<=n){
			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){
						cur2[k.b]=1;
					}
				}
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	int xx=tt[low].b;
	//cout<<no.a<<":"<<no.b<<endl;
	//cout<<xx<<":"<<endl;
	if(dist[xx]==(ans/(llo)aa)){
		answer(xx,no.a);
		return;
	}
	llo zz=xx;
	while(zz>=0){
		vis[zz]=1;
		//cout<<zz<<".";
		zz=ba[zz];
	}
	//cout<<endl;
	low=0;
	/*for(auto j:tt){
		cout<<j.a<<"<<"<<j.b<<endl;
	}
	cout<<endl<<endl;
	for(int i=0;i<n;i++){
		cout<<dist[i]<<"<";
	}
	cout<<endl;*/
	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(tt[i].b==3){
						cout<<k.a<<"{{"<<k.b<<endl;
						cout<<dist[k.a]<<"}}"<<dist[x]<<endl;
					}*/
					if(dist[k.a]==dist[x]-1){
						cur2[k.b]=1;
					/*	if(tt[i].b==3){
							cout<<k.b<<"!!"<<endl;
						}*/
					}
				}
			}
			if(ask(cur2)==ans){
				/*cout<<low+(1<<j)<<":::"<<endl;
				for(auto ii:cur2){
					cout<<ii;
				}
				cout<<endl;
				cout<<ask(cur2)<<endl;*/
				low+=(1<<j);
			}
		}
	}
//	cout<<low<<endl;
	//cout<<tt[low].b<<",,"<<endl;
	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);*/



}

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