oj.uz

Submission #121440

# Submission time Handle Problem Language Result Execution time Memory
121440 2019-06-26T14:13:09 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 342 ms 14972 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() % 4 == 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){
	srand(7);

	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 4984 KB Output is correct
2 Correct 6 ms 4984 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 5020 KB Output is correct
6 Correct 6 ms 5020 KB Output is correct
7 Correct 6 ms 5020 KB Output is correct
8 Correct 6 ms 5008 KB Output is correct
9 Correct 7 ms 5028 KB Output is correct
10 Correct 6 ms 5104 KB Output is correct
11 Correct 6 ms 5024 KB Output is correct
12 Correct 6 ms 5108 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5104 KB Output is correct
2 Correct 41 ms 6004 KB Output is correct
3 Correct 252 ms 14464 KB Output is correct
4 Correct 207 ms 14456 KB Output is correct
5 Correct 288 ms 14464 KB Output is correct
6 Correct 229 ms 14468 KB Output is correct
7 Correct 236 ms 14452 KB Output is correct
8 Correct 219 ms 14468 KB Output is correct
9 Correct 239 ms 14476 KB Output is correct
10 Correct 245 ms 14508 KB Output is correct
11 Correct 279 ms 14268 KB Output is correct
12 Correct 265 ms 14268 KB Output is correct
13 Correct 310 ms 14264 KB Output is correct
14 Correct 258 ms 14272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5988 KB Output is correct
2 Correct 55 ms 7096 KB Output is correct
3 Correct 87 ms 7924 KB Output is correct
4 Correct 181 ms 14272 KB Output is correct
5 Correct 276 ms 14256 KB Output is correct
6 Correct 243 ms 14276 KB Output is correct
7 Correct 173 ms 14260 KB Output is correct
8 Correct 179 ms 14252 KB Output is correct
9 Correct 168 ms 14272 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5100 KB Output is correct
2 Correct 42 ms 6012 KB Output is correct
3 Correct 179 ms 12616 KB Output is correct
4 Correct 267 ms 14564 KB Output is correct
5 Correct 342 ms 14464 KB Output is correct
6 Correct 280 ms 14416 KB Output is correct
7 Correct 277 ms 14484 KB Output is correct
8 Correct 207 ms 14444 KB Output is correct
9 Correct 240 ms 14492 KB Output is correct
10 Correct 234 ms 14460 KB Output is correct
11 Correct 231 ms 14328 KB Output is correct
12 Correct 297 ms 14276 KB Output is correct
13 Correct 241 ms 14276 KB Output is correct
14 Correct 251 ms 14268 KB Output is correct
15 Correct 266 ms 14544 KB Output is correct
16 Correct 234 ms 14452 KB Output is correct
17 Correct 306 ms 14268 KB Output is correct
18 Correct 275 ms 14396 KB Output is correct
19 Correct 221 ms 14476 KB Output is correct
20 Correct 238 ms 14336 KB Output is correct
21 Correct 197 ms 14964 KB Output is correct
22 Correct 205 ms 14960 KB Output is correct
23 Correct 239 ms 14972 KB Output is correct
24 Correct 234 ms 14920 KB Output is correct
25 Correct 215 ms 14356 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 6120 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 28 ms 6120 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -