oj.uz

Submission #121434

# Submission time Handle Problem Language Result Execution time Memory
121434 2019-06-26T14:08:26 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 369 ms 14988 KB 
#include <bits/stdc++.h>
#include "highway.h"
 
using namespace std;
 
const int MAXN = 1e5 + 7;
 
long long ask(const vector<int> &w);
void answer(int s, int t);
 
mt19937 mt();
 
long long n, m;
vector<int> adj[MAXN], idx[MAXN], w;
bool used[MAXN];

long long a, b;
long long sm;
 
vector<pair<int, int> > bfs(int x){
	queue<int> q;
 
	for(int i = 0; i < n; i++){
		used[i] = false;
	}
 
	q.push(x);
	
	vector<pair<int, int> > v;
 
	while(!q.empty()){
		int u = q.front();
		q.pop();
 
		if(used[u]){
			continue;
		}
		used[u] = true;
 
		for(int i = 0; i < adj[u].size(); i++){
			int to = adj[u][i];
			int j = idx[u][i];
 
			if(!used[to]){
				q.push(to);
				v.push_back({j, to});
			}
		}
	}
 
	return v;
}
 
int away(int x, const vector<int> &U, const vector<int> &V){
	vector<pair<int, int> > v = bfs(x);
 
	while((int)v.size() != m);

	int l = 0, r = (int)v.size() - 1;
 
	while(l != r){
		int mid = (l + r) >> 1;
		 
		for(int i = 0; i < m; i++){
			w[i] = 0;
		}

		for(int i = 0; i <= mid; i++){
			w[ v[i].first ] = 1;
		}

		long long score = ask(w); 

		if(score == (sm / a) * b){
			r = mid;
		}
		else{
			l = mid + 1;
		}
	}

	if(rand() % 3 == 0){
		int idx = v[l].first;

		if(U[idx] == v[l].second){
			return V[idx];
		}

		return U[idx];
	}

	return v[l].second;
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	n = N;
	m = U.size();
 
	for(int i = 0; i < m; i++){
		adj[V[i]].push_back(U[i]);
		adj[U[i]].push_back(V[i]);
 
		idx[V[i]].push_back(i);
		idx[U[i]].push_back(i);
		w.push_back(0);
	}
 
	sm = ask(w);
	a = A;
	b = B;
 
	int l = 0, r = m - 1;
 
	while(l != r){
		int mid = (l + r) / 2;
 
		for(int i = 0; i < m; i++){
			w[i] = 0; 
		}
		for(int i = mid + 1; i <= r; i++){
			w[i] = 1;
		}
 
		long long score = ask(w);
		score -= sm;
 
		if(score){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}
 
	int x, y;
 
	x = away(U[l], U, V);
 
	y = away(x, U, V);
 
	answer(x, y);
}
/*
9 1 2
4 8
4 2
8 0
2 5
2 7
2 3
0 1
0 6
*/

Compilation message

highway.cpp: In function 'std::vector<std::pair<int, int> > bfs(int)':
highway.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++){
                  ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5024 KB Output is correct
2 Correct 6 ms 5024 KB Output is correct
3 Correct 6 ms 5020 KB Output is correct
4 Correct 6 ms 5028 KB Output is correct
5 Correct 7 ms 5028 KB Output is correct
6 Correct 7 ms 5032 KB Output is correct
7 Correct 6 ms 5020 KB Output is correct
8 Correct 6 ms 5024 KB Output is correct
9 Correct 7 ms 5024 KB Output is correct
10 Correct 6 ms 5020 KB Output is correct
11 Correct 7 ms 5028 KB Output is correct
12 Correct 6 ms 5020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5104 KB Output is correct
2 Correct 44 ms 6044 KB Output is correct
3 Correct 320 ms 14472 KB Output is correct
4 Correct 232 ms 14468 KB Output is correct
5 Correct 236 ms 14464 KB Output is correct
6 Correct 233 ms 14448 KB Output is correct
7 Correct 352 ms 14452 KB Output is correct
8 Correct 316 ms 14456 KB Output is correct
9 Correct 341 ms 14448 KB Output is correct
10 Correct 324 ms 14480 KB Output is correct
11 Correct 369 ms 14336 KB Output is correct
12 Correct 341 ms 14252 KB Output is correct
13 Correct 308 ms 14284 KB Output is correct
14 Correct 250 ms 14256 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5988 KB Output is correct
2 Correct 24 ms 7096 KB Output is correct
3 Correct 42 ms 7908 KB Output is correct
4 Correct 229 ms 14264 KB Output is correct
5 Correct 270 ms 14252 KB Output is correct
6 Correct 279 ms 14256 KB Output is correct
7 Correct 248 ms 14340 KB Output is correct
8 Correct 284 ms 14256 KB Output is correct
9 Correct 256 ms 14272 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5096 KB Output is correct
2 Correct 30 ms 6020 KB Output is correct
3 Correct 159 ms 12608 KB Output is correct
4 Correct 323 ms 14460 KB Output is correct
5 Correct 335 ms 14452 KB Output is correct
6 Correct 322 ms 14456 KB Output is correct
7 Correct 213 ms 14484 KB Output is correct
8 Correct 238 ms 14468 KB Output is correct
9 Correct 305 ms 14460 KB Output is correct
10 Correct 243 ms 14520 KB Output is correct
11 Correct 277 ms 14268 KB Output is correct
12 Correct 261 ms 14264 KB Output is correct
13 Correct 304 ms 14364 KB Output is correct
14 Correct 267 ms 14268 KB Output is correct
15 Correct 235 ms 14448 KB Output is correct
16 Correct 245 ms 14452 KB Output is correct
17 Correct 267 ms 14256 KB Output is correct
18 Correct 253 ms 14372 KB Output is correct
19 Correct 231 ms 14484 KB Output is correct
20 Correct 247 ms 14272 KB Output is correct
21 Correct 202 ms 14968 KB Output is correct
22 Correct 202 ms 14964 KB Output is correct
23 Correct 229 ms 14988 KB Output is correct
24 Correct 225 ms 14936 KB Output is correct
25 Correct 269 ms 14384 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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