oj.uz

Submission #99469

# Submission time Handle Problem Language Result Execution time Memory
99469 2019-03-04T09:14:19 Z tugushka Highway Tolls (IOI18_highway) C++14
12 / 100
 907 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;

int findEnd( int start, int startParent){
	edg.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) );
			}
		}
	}

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

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

	// 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;
	}

	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;
	}


	return ans[l].second;
}

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 s = 0;
	int t = findEnd( s, -1 );

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

10 9 1 5 0 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 248 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 252 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 248 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 252 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 248 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 32 ms 1428 KB Output is correct
3 Correct 148 ms 9844 KB Output is correct
4 Correct 181 ms 9768 KB Output is correct
5 Correct 187 ms 9752 KB Output is correct
6 Correct 166 ms 9716 KB Output is correct
7 Correct 169 ms 9832 KB Output is correct
8 Correct 194 ms 9724 KB Output is correct
9 Correct 173 ms 9724 KB Output is correct
10 Correct 176 ms 9720 KB Output is correct
11 Correct 175 ms 9200 KB Output is correct
12 Correct 175 ms 9224 KB Output is correct
13 Correct 162 ms 9280 KB Output is correct
14 Correct 186 ms 9208 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1284 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 296 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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