oj.uz

Submission #121447

# Submission time Handle Problem Language Result Execution time Memory
121447 2019-06-26T14:16:43 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 348 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 cnt_away = 0;
 
bool in[2] = {false, false}; 

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(in[cnt_away]){
		int idx = v[l].first;
		cnt_away++;

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

		return U[idx];
	}

	cnt_away++;

	return v[l].second;
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	srand(time(NULL));

	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 5108 KB Output is correct
2 Correct 6 ms 5024 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 5028 KB Output is correct
5 Correct 6 ms 5020 KB Output is correct
6 Correct 7 ms 4984 KB Output is correct
7 Correct 6 ms 5024 KB Output is correct
8 Correct 6 ms 5020 KB Output is correct
9 Correct 7 ms 4924 KB Output is correct
10 Correct 6 ms 5024 KB Output is correct
11 Correct 0 ms 5024 KB Output is correct
12 Correct 6 ms 4960 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5096 KB Output is correct
2 Correct 40 ms 6020 KB Output is correct
3 Correct 302 ms 14472 KB Output is correct
4 Correct 216 ms 14532 KB Output is correct
5 Correct 254 ms 14460 KB Output is correct
6 Correct 227 ms 14484 KB Output is correct
7 Correct 306 ms 14484 KB Output is correct
8 Correct 254 ms 14460 KB Output is correct
9 Correct 248 ms 14464 KB Output is correct
10 Correct 234 ms 14464 KB Output is correct
11 Correct 289 ms 14268 KB Output is correct
12 Correct 243 ms 14264 KB Output is correct
13 Correct 232 ms 14372 KB Output is correct
14 Correct 269 ms 14280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5984 KB Output is correct
2 Correct 53 ms 7088 KB Output is correct
3 Correct 87 ms 8088 KB Output is correct
4 Correct 157 ms 14268 KB Output is correct
5 Correct 179 ms 14272 KB Output is correct
6 Correct 217 ms 14260 KB Output is correct
7 Correct 121 ms 14256 KB Output is correct
8 Correct 146 ms 14288 KB Output is correct
9 Correct 160 ms 14260 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 24 ms 6160 KB Output is correct
3 Correct 206 ms 12608 KB Output is correct
4 Correct 337 ms 14468 KB Output is correct
5 Correct 249 ms 14464 KB Output is correct
6 Correct 249 ms 14452 KB Output is correct
7 Correct 244 ms 14464 KB Output is correct
8 Correct 228 ms 14448 KB Output is correct
9 Correct 258 ms 14468 KB Output is correct
10 Correct 348 ms 14472 KB Output is correct
11 Correct 210 ms 14304 KB Output is correct
12 Correct 245 ms 14276 KB Output is correct
13 Correct 347 ms 14272 KB Output is correct
14 Correct 281 ms 14336 KB Output is correct
15 Correct 226 ms 14456 KB Output is correct
16 Correct 297 ms 14472 KB Output is correct
17 Correct 287 ms 14252 KB Output is correct
18 Correct 272 ms 14280 KB Output is correct
19 Correct 253 ms 14456 KB Output is correct
20 Correct 248 ms 14252 KB Output is correct
21 Correct 245 ms 14976 KB Output is correct
22 Correct 199 ms 14964 KB Output is correct
23 Correct 241 ms 14988 KB Output is correct
24 Correct 220 ms 14924 KB Output is correct
25 Correct 318 ms 14352 KB Output is correct

Subtask #5
0 / 18.0

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