oj.uz

Submission #99477

# Submission time Handle Problem Language Result Execution time Memory
99477 2019-03-04T10:08:04 Z tugushka Highway Tolls (IOI18_highway) C++14
51 / 100
 879 ms 262148 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 260 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 248 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 296 KB Output is correct
2 Correct 21 ms 1412 KB Output is correct
3 Correct 181 ms 9720 KB Output is correct
4 Correct 195 ms 9848 KB Output is correct
5 Correct 196 ms 9720 KB Output is correct
6 Correct 187 ms 9716 KB Output is correct
7 Correct 175 ms 9824 KB Output is correct
8 Correct 187 ms 9716 KB Output is correct
9 Correct 197 ms 9716 KB Output is correct
10 Correct 208 ms 9712 KB Output is correct
11 Correct 201 ms 9204 KB Output is correct
12 Correct 196 ms 9336 KB Output is correct
13 Correct 187 ms 9212 KB Output is correct
14 Correct 181 ms 9212 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1280 KB Output is correct
2 Correct 43 ms 2376 KB Output is correct
3 Correct 51 ms 3300 KB Output is correct
4 Correct 173 ms 9212 KB Output is correct
5 Correct 175 ms 9204 KB Output is correct
6 Correct 156 ms 9212 KB Output is correct
7 Correct 168 ms 9208 KB Output is correct
8 Correct 163 ms 9208 KB Output is correct
9 Correct 160 ms 9200 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 21 ms 1400 KB Output is correct
3 Correct 151 ms 8024 KB Output is correct
4 Correct 199 ms 9720 KB Output is correct
5 Correct 174 ms 9844 KB Output is correct
6 Correct 180 ms 9712 KB Output is correct
7 Correct 174 ms 9724 KB Output is correct
8 Correct 198 ms 9716 KB Output is correct
9 Correct 232 ms 9852 KB Output is correct
10 Correct 186 ms 9720 KB Output is correct
11 Correct 187 ms 9204 KB Output is correct
12 Correct 205 ms 9256 KB Output is correct
13 Correct 194 ms 9200 KB Output is correct
14 Correct 195 ms 9216 KB Output is correct
15 Correct 197 ms 9720 KB Output is correct
16 Correct 161 ms 9716 KB Output is correct
17 Correct 169 ms 9208 KB Output is correct
18 Correct 209 ms 9216 KB Output is correct
19 Correct 187 ms 9720 KB Output is correct
20 Correct 197 ms 9204 KB Output is correct
21 Correct 177 ms 10220 KB Output is correct
22 Correct 179 ms 10224 KB Output is correct
23 Correct 210 ms 10096 KB Output is correct
24 Correct 167 ms 10060 KB Output is correct
25 Correct 194 ms 9336 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 865 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 879 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -