oj.uz

Submission #119585

# Submission time Handle Problem Language Result Execution time Memory
119585 2019-06-21T12:14:30 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 352 ms 15096 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 / b) * a == sm){
			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 7 ms 5024 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 5 ms 5028 KB Output is correct
4 Correct 8 ms 5024 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 8 ms 4984 KB Output is correct
7 Correct 6 ms 5024 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5024 KB Output is correct
11 Correct 6 ms 5020 KB Output is correct
12 Correct 6 ms 5024 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5104 KB Output is correct
2 Correct 25 ms 6036 KB Output is correct
3 Correct 277 ms 14468 KB Output is correct
4 Correct 224 ms 14464 KB Output is correct
5 Correct 224 ms 14464 KB Output is correct
6 Correct 253 ms 14468 KB Output is correct
7 Correct 218 ms 14460 KB Output is correct
8 Correct 244 ms 14532 KB Output is correct
9 Correct 174 ms 14456 KB Output is correct
10 Correct 228 ms 14560 KB Output is correct
11 Correct 277 ms 14264 KB Output is correct
12 Correct 282 ms 14268 KB Output is correct
13 Correct 280 ms 14260 KB Output is correct
14 Correct 267 ms 14372 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6000 KB Output is correct
2 Correct 50 ms 7204 KB Output is correct
3 Correct 48 ms 7928 KB Output is correct
4 Correct 188 ms 14396 KB Output is correct
5 Correct 207 ms 14264 KB Output is correct
6 Correct 137 ms 14260 KB Output is correct
7 Correct 266 ms 14260 KB Output is correct
8 Correct 149 ms 14268 KB Output is correct
9 Correct 158 ms 14256 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5104 KB Output is correct
2 Correct 21 ms 6008 KB Output is correct
3 Correct 224 ms 12716 KB Output is correct
4 Correct 238 ms 14616 KB Output is correct
5 Correct 225 ms 14456 KB Output is correct
6 Correct 222 ms 14464 KB Output is correct
7 Correct 232 ms 14468 KB Output is correct
8 Correct 273 ms 14468 KB Output is correct
9 Correct 250 ms 14504 KB Output is correct
10 Correct 191 ms 14448 KB Output is correct
11 Correct 289 ms 14268 KB Output is correct
12 Correct 301 ms 14276 KB Output is correct
13 Correct 282 ms 14272 KB Output is correct
14 Correct 352 ms 14252 KB Output is correct
15 Correct 240 ms 14428 KB Output is correct
16 Correct 219 ms 14524 KB Output is correct
17 Correct 248 ms 14272 KB Output is correct
18 Correct 257 ms 14280 KB Output is correct
19 Correct 241 ms 14424 KB Output is correct
20 Correct 259 ms 14288 KB Output is correct
21 Correct 217 ms 14960 KB Output is correct
22 Correct 204 ms 14964 KB Output is correct
23 Correct 227 ms 15096 KB Output is correct
24 Correct 249 ms 14924 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 33 ms 6124 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 45 ms 6120 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -