oj.uz

Submission #121622

# Submission time Handle Problem Language Result Execution time Memory
121622 2019-06-26T20:53:16 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 324 ms 17200 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 + 2;
	}
 
	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:35:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i = 0; i < adj[u].size(); i++){
                        ~~^~~~~~~~~~~~~~~
highway.cpp:37: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 4944 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5032 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 5032 KB Output is correct
9 Correct 6 ms 5116 KB Output is correct
10 Correct 6 ms 5036 KB Output is correct
11 Correct 6 ms 5032 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 11 ms 5108 KB Output is correct
2 Correct 26 ms 6312 KB Output is correct
3 Correct 259 ms 16484 KB Output is correct
4 Correct 259 ms 16500 KB Output is correct
5 Correct 257 ms 16616 KB Output is correct
6 Correct 272 ms 16472 KB Output is correct
7 Correct 280 ms 16520 KB Output is correct
8 Correct 260 ms 16588 KB Output is correct
9 Correct 275 ms 16492 KB Output is correct
10 Correct 278 ms 16488 KB Output is correct
11 Correct 288 ms 16264 KB Output is correct
12 Correct 297 ms 16368 KB Output is correct
13 Correct 274 ms 16276 KB Output is correct
14 Correct 307 ms 16272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6284 KB Output is correct
2 Correct 33 ms 7564 KB Output is correct
3 Correct 66 ms 8532 KB Output is correct
4 Correct 195 ms 16276 KB Output is correct
5 Correct 309 ms 16248 KB Output is correct
6 Correct 291 ms 16264 KB Output is correct
7 Correct 158 ms 16264 KB Output is correct
8 Correct 204 ms 16260 KB Output is correct
9 Correct 169 ms 16252 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5116 KB Output is correct
2 Correct 54 ms 6324 KB Output is correct
3 Correct 207 ms 14452 KB Output is correct
4 Correct 249 ms 16476 KB Output is correct
5 Correct 272 ms 16476 KB Output is correct
6 Correct 247 ms 16492 KB Output is correct
7 Correct 268 ms 16492 KB Output is correct
8 Correct 275 ms 16472 KB Output is correct
9 Correct 247 ms 16516 KB Output is correct
10 Correct 298 ms 16492 KB Output is correct
11 Correct 309 ms 16272 KB Output is correct
12 Correct 319 ms 16352 KB Output is correct
13 Correct 310 ms 16264 KB Output is correct
14 Correct 317 ms 16276 KB Output is correct
15 Correct 263 ms 16628 KB Output is correct
16 Correct 241 ms 16508 KB Output is correct
17 Correct 288 ms 16312 KB Output is correct
18 Correct 297 ms 16260 KB Output is correct
19 Correct 267 ms 16492 KB Output is correct
20 Correct 264 ms 16264 KB Output is correct
21 Correct 189 ms 17184 KB Output is correct
22 Correct 235 ms 17196 KB Output is correct
23 Correct 266 ms 17200 KB Output is correct
24 Correct 267 ms 16992 KB Output is correct
25 Correct 303 ms 16480 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6344 KB Output is correct
2 Incorrect 40 ms 6364 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 28 ms 6376 KB Output is correct
2 Correct 42 ms 6416 KB Output is correct
3 Partially correct 324 ms 16960 KB Output is partially correct
4 Incorrect 304 ms 17116 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -