Submission #99477

#	Time	Username	Problem	Language	Result	Execution time	Memory
99477		tugushka	Highway Tolls (IOI18_highway)	C++14	51 / 100	879 ms	262148 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
#define mp make_pair
#define pb push_back
using namespace std;

using pii = pair < int, int >;

vector < vector < pii > > to;
vector < pii > edg, ans;
vector<int> w;
int n, m, A, B;
long long L;

void bfs( int start, int startParent){
	ans.clear();
	queue < pii > q;
	q.push( mp( start, startParent ) );

	while( !q.empty() ){
		int sz = q.size();
		while(sz--){
			pii u = q.front();
			q.pop();
			for( pii v : to[u.first] ){
				if( v.first == u.second ) continue;
				q.push( mp( v.first, u.first ) );
				ans.push_back( mp( v.second, v.first) );
			}
		}
	}
}

int findEnd( int start, int startParent ){
	bfs( start, startParent );

	fill( w.begin(), w.end(), 0 );
	L = ask( w );

	/*
	cerr << "############\n";
	cerr << "start : "<< start << ' ' << startParent << endl;
	for(int i = 0 ; i < ans.size() ; i++){
		cerr << ans[i].second << ' ' << ans[i].first << endl;
	}*/

	if( ans.empty() ) return start;

	// cerr << L << endl;

	long long now;
	int l = 0, r = ans.size()-1;
	while( l+1 < r ){
		int mid = (l+r)>>1;

		fill( w.begin(), w.end(), 0 );
		for(int i = mid ; i <= r ; i++){
			w[ans[i].first] = 1;
		}

		now = ask( w );

		// cerr << l << ' ' << r << " : " << mid << ' ' << now << endl;

		if( now > L ) l = mid;
		else r = mid-1;
	}

	// cerr << l << ' ' << r << endl;

	if( l != r ){
		fill( w.begin(), w.end(), 0 );
		w[ ans[l+1].first ] = 1;
		now = ask( w );
		if( now > L ) return ans[l+1].second;

		fill( w.begin(), w.end(), 0 );
		w[ ans[l].first ] = 1;
		now = ask( w );
		if( now > L ) return ans[l].second;

		return start;
	}

	fill( w.begin(), w.end(), 0 );
	w[ ans[l].first ] = 1;
	now = ask( w );
	if( now > L ) return ans[l].second;

	return start;
}

int findEdge( int start ){
	bfs( start, -1 );

	fill( w.begin(), w.end(), 0 );
	L = ask( w );

	long long now;
	int l = 0, r = ans.size()-1;
	while( l+1 < r ){
		int mid = (l+r)>>1;

		fill( w.begin(), w.end(), 0 );
		for(int i = mid ; i <= r ; i++){
			w[ans[i].first] = 1;
		}

		now = ask( w );

		// cerr << l << ' ' << r << " : " << mid << ' ' << now << endl;

		if( now > L ) l = mid;
		else r = mid-1;
	}

	if( l != r ){
		fill( w.begin(), w.end(), 0 );
		w[ ans[l].first ] = 1;
		now = ask( w );
		if( now > L ) return ans[l].first;

		fill( w.begin(), w.end(), 0 );
		w[ ans[l+1].first ] = 1;
		now = ask( w );
		if( now > L ) return ans[l+1].first;

		return start;
	}

	return ans[l].first;
}

void find_pair(int N, vector<int> U, vector<int> V, int _A, int _B) {
	n = N; A = _A; B = _B; m = U.size();
	w.resize(m);
	to.resize(n+1);

	for(int i = 0 ; i < m ; i++){
		to[ U[i] ].pb( mp( V[i], i ) );
		to[ V[i] ].pb( mp( U[i], i ) );
		edg.push_back( mp( V[i], U[i] ) );
	}

	int e = findEdge( 0 );
	// cerr << "### " << edg[e].first << ' ' << edg[e].second << endl;

	int s = findEnd( edg[e].first, edg[e].second );
	int t = findEnd( edg[e].second, edg[e].first );

	// cerr << "## " << s << ' ' << t << endl;

	answer( s, t );
}
/*
4 3 1 3 1 3
0 1
0 2
0 3

10 9 1 5 3 9
0 1
0 2
2 9
1 3
1 4
1 5
3 6
4 7
4 8

*/

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