oj.uz

Submission #119598

# Submission time Handle Problem Language Result Execution time Memory
119598 2019-06-21T12:36:35 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 313 ms 14984 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);
 
	assert((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;
		}
	}
 
	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 4984 KB Output is correct
2 Correct 6 ms 5028 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 5024 KB Output is correct
6 Correct 6 ms 5104 KB Output is correct
7 Correct 6 ms 5028 KB Output is correct
8 Correct 6 ms 4988 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5028 KB Output is correct
11 Correct 6 ms 5024 KB Output is correct
12 Correct 7 ms 5028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5096 KB Output is correct
2 Correct 19 ms 6000 KB Output is correct
3 Correct 252 ms 14460 KB Output is correct
4 Correct 242 ms 14460 KB Output is correct
5 Correct 252 ms 14464 KB Output is correct
6 Correct 250 ms 14564 KB Output is correct
7 Correct 245 ms 14580 KB Output is correct
8 Correct 201 ms 14460 KB Output is correct
9 Correct 247 ms 14476 KB Output is correct
10 Correct 248 ms 14664 KB Output is correct
11 Correct 256 ms 14312 KB Output is correct
12 Correct 250 ms 14264 KB Output is correct
13 Correct 242 ms 14268 KB Output is correct
14 Correct 258 ms 14260 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5984 KB Output is correct
2 Correct 47 ms 7080 KB Output is correct
3 Correct 55 ms 7924 KB Output is correct
4 Correct 138 ms 14332 KB Output is correct
5 Correct 190 ms 14196 KB Output is correct
6 Correct 191 ms 14284 KB Output is correct
7 Correct 114 ms 14260 KB Output is correct
8 Correct 183 ms 14260 KB Output is correct
9 Correct 138 ms 14256 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 24 ms 6036 KB Output is correct
3 Correct 200 ms 12604 KB Output is correct
4 Correct 204 ms 14452 KB Output is correct
5 Correct 257 ms 14472 KB Output is correct
6 Correct 203 ms 14468 KB Output is correct
7 Correct 242 ms 14544 KB Output is correct
8 Correct 230 ms 14456 KB Output is correct
9 Correct 313 ms 14460 KB Output is correct
10 Correct 242 ms 14468 KB Output is correct
11 Correct 209 ms 14280 KB Output is correct
12 Correct 257 ms 14256 KB Output is correct
13 Correct 263 ms 14264 KB Output is correct
14 Correct 255 ms 14276 KB Output is correct
15 Correct 242 ms 14428 KB Output is correct
16 Correct 230 ms 14468 KB Output is correct
17 Correct 267 ms 14272 KB Output is correct
18 Correct 240 ms 14264 KB Output is correct
19 Correct 221 ms 14640 KB Output is correct
20 Correct 278 ms 14252 KB Output is correct
21 Correct 172 ms 14972 KB Output is correct
22 Correct 222 ms 14956 KB Output is correct
23 Correct 232 ms 14984 KB Output is correct
24 Correct 229 ms 14936 KB Output is correct
25 Correct 265 ms 14352 KB Output is correct

Subtask #5
0 / 18.0

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