oj.uz

Submission #99476

# Submission time Handle Problem Language Result Execution time Memory
99476 2019-03-04T09:51:51 Z tugushka Highway Tolls (IOI18_highway) C++14
7 / 100
 863 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].first ] = 1;
		now = ask( w );
		if( now > L ) return ans[l].second;

		fill( w.begin(), w.end(), 0 );
		w[ ans[l+1].first ] = 1;
		now = ask( w );
		if( now > L ) return ans[l+1].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( 1 );
	// 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 2 9
0 1
0 2
2 9
1 3
1 4
1 5
3 6
4 7
4 8

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 21 ms 1408 KB Output is correct
3 Correct 178 ms 9724 KB Output is correct
4 Correct 168 ms 9728 KB Output is correct
5 Correct 215 ms 9736 KB Output is correct
6 Correct 162 ms 9728 KB Output is correct
7 Correct 197 ms 9720 KB Output is correct
8 Correct 184 ms 9720 KB Output is correct
9 Correct 178 ms 9716 KB Output is correct
10 Correct 154 ms 9740 KB Output is correct
11 Correct 206 ms 9204 KB Output is correct
12 Correct 204 ms 9240 KB Output is correct
13 Correct 203 ms 9204 KB Output is correct
14 Correct 186 ms 9332 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1336 KB Output is correct
2 Incorrect 33 ms 2360 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 14 ms 1416 KB Output is correct
3 Correct 119 ms 8024 KB Output is correct
4 Correct 194 ms 9720 KB Output is correct
5 Correct 205 ms 9768 KB Output is correct
6 Correct 180 ms 9720 KB Output is correct
7 Correct 182 ms 9820 KB Output is correct
8 Correct 202 ms 9720 KB Output is correct
9 Correct 191 ms 9756 KB Output is correct
10 Correct 189 ms 9744 KB Output is correct
11 Correct 206 ms 9196 KB Output is correct
12 Correct 222 ms 9204 KB Output is correct
13 Correct 204 ms 9200 KB Output is correct
14 Correct 189 ms 9252 KB Output is correct
15 Correct 163 ms 9724 KB Output is correct
16 Incorrect 174 ms 9716 KB Output is incorrect: {s, t} is wrong.
17 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 858 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 863 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -