oj.uz

Submission #121625

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

long long a, b;
long long sm;

queue<long long> q;

void bfs(long long x){
	for(long long i = 0; i <= n; i++){
		d[i] = n + m + 2;
	}
 
	assert(q.empty());

	q.push(x);
	d[x] = 0; 
 
	while(!q.empty()){
		long long u = q.front();
		q.pop();

		for(long long i = 0; i < adj[u].size(); i++){
			long long to = adj[u][i];
			long long j = idx[u][i];
 
			if(d[to] > d[u] + 1){
				d[to] = d[u] + 1;
				q.push(to);
			}
		}
	}
}

bool cmp(pair<long long, long long> lvalue, pair<long long, long long> rvalue){
	return d[lvalue.second] < d[rvalue.second];
}

long long away(int x, const vector<int> &U, const vector<int> &V){
	bfs(x);
 
	vector<pair<long long, long long> > v;

	for(int i = 0; i < m; i++){
		v.push_back({i, d[U[i]] <= d[V[i]] ? V[i] : U[i]});
	}

	sort(v.begin(), v.end(), cmp);

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

		for(long long 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){
	srand(time(NULL));

	n = N;
	m = U.size();
 
	for(long long 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;
 
	long long l = 0, r = m - 1;
 
	while(l != r){
		long long mid = (l + r) / 2;
 
		for(long long i = 0; i < m; i++){
			w[i] = 0; 
		}
		for(long long i = mid + 1; i <= r; i++){
			w[i] = 1;
		}
 
		long long score = ask(w);
		score -= sm;
 
		if(score){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}
 
	long long x, y;
 
	x = away(V[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 'void bfs(long long int)':
highway.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i = 0; i < adj[u].size(); i++){
                        ~~^~~~~~~~~~~~~~~
highway.cpp:39:14: warning: unused variable 'j' [-Wunused-variable]
    long long j = idx[u][i];
              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5028 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 5036 KB Output is correct
5 Correct 6 ms 5036 KB Output is correct
6 Correct 6 ms 5036 KB Output is correct
7 Correct 6 ms 5032 KB Output is correct
8 Correct 6 ms 5116 KB Output is correct
9 Correct 6 ms 5116 KB Output is correct
10 Correct 7 ms 5032 KB Output is correct
11 Correct 7 ms 5116 KB Output is correct
12 Correct 9 ms 5008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 35 ms 6300 KB Output is correct
3 Correct 273 ms 16496 KB Output is correct
4 Correct 274 ms 16508 KB Output is correct
5 Correct 315 ms 16480 KB Output is correct
6 Correct 254 ms 16496 KB Output is correct
7 Correct 291 ms 16488 KB Output is correct
8 Correct 249 ms 16496 KB Output is correct
9 Correct 261 ms 16484 KB Output is correct
10 Correct 280 ms 16500 KB Output is correct
11 Correct 300 ms 16268 KB Output is correct
12 Correct 320 ms 16264 KB Output is correct
13 Correct 379 ms 16260 KB Output is correct
14 Correct 306 ms 16264 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6328 KB Output is correct
2 Correct 51 ms 7696 KB Output is correct
3 Correct 57 ms 8624 KB Output is correct
4 Correct 234 ms 16260 KB Output is correct
5 Correct 238 ms 16260 KB Output is correct
6 Correct 204 ms 16264 KB Output is correct
7 Correct 184 ms 16264 KB Output is correct
8 Correct 215 ms 16272 KB Output is correct
9 Correct 194 ms 16264 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 33 ms 6320 KB Output is correct
3 Correct 165 ms 14424 KB Output is correct
4 Correct 270 ms 16472 KB Output is correct
5 Correct 269 ms 16484 KB Output is correct
6 Correct 258 ms 16500 KB Output is correct
7 Correct 284 ms 16512 KB Output is correct
8 Correct 267 ms 16480 KB Output is correct
9 Correct 266 ms 16588 KB Output is correct
10 Correct 306 ms 16508 KB Output is correct
11 Correct 335 ms 16248 KB Output is correct
12 Correct 327 ms 16268 KB Output is correct
13 Correct 296 ms 16276 KB Output is correct
14 Correct 338 ms 16264 KB Output is correct
15 Correct 289 ms 16492 KB Output is correct
16 Correct 241 ms 16544 KB Output is correct
17 Correct 340 ms 16264 KB Output is correct
18 Correct 269 ms 16288 KB Output is correct
19 Correct 284 ms 16496 KB Output is correct
20 Correct 275 ms 16324 KB Output is correct
21 Correct 203 ms 17196 KB Output is correct
22 Correct 167 ms 17184 KB Output is correct
23 Correct 232 ms 17108 KB Output is correct
24 Correct 249 ms 17012 KB Output is correct
25 Correct 285 ms 16372 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6340 KB Output is correct
2 Incorrect 31 ms 6376 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6332 KB Output is correct
2 Correct 42 ms 6364 KB Output is correct
3 Partially correct 334 ms 16940 KB Output is partially correct
4 Incorrect 302 ms 17116 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -