oj.uz

Submission #121620

# Submission time Handle Problem Language Result Execution time Memory
121620 2019-06-26T20:52:03 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 406 ms 17244 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 5116 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5160 KB Output is correct
4 Correct 6 ms 5040 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5028 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5036 KB Output is correct
9 Correct 6 ms 5032 KB Output is correct
10 Correct 6 ms 5052 KB Output is correct
11 Correct 6 ms 5036 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5108 KB Output is correct
2 Correct 29 ms 6312 KB Output is correct
3 Correct 310 ms 16508 KB Output is correct
4 Correct 277 ms 16504 KB Output is correct
5 Correct 297 ms 16500 KB Output is correct
6 Correct 317 ms 16500 KB Output is correct
7 Correct 268 ms 16548 KB Output is correct
8 Correct 291 ms 16500 KB Output is correct
9 Correct 272 ms 16500 KB Output is correct
10 Correct 268 ms 16500 KB Output is correct
11 Correct 311 ms 16256 KB Output is correct
12 Correct 315 ms 16368 KB Output is correct
13 Correct 319 ms 16276 KB Output is correct
14 Correct 280 ms 16344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6264 KB Output is correct
2 Correct 42 ms 7512 KB Output is correct
3 Correct 52 ms 8528 KB Output is correct
4 Correct 210 ms 16260 KB Output is correct
5 Correct 158 ms 16300 KB Output is correct
6 Correct 212 ms 16476 KB Output is correct
7 Correct 166 ms 16260 KB Output is correct
8 Correct 222 ms 16264 KB Output is correct
9 Correct 164 ms 16252 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5108 KB Output is correct
2 Correct 32 ms 6304 KB Output is correct
3 Correct 200 ms 14420 KB Output is correct
4 Correct 287 ms 16484 KB Output is correct
5 Correct 244 ms 16480 KB Output is correct
6 Correct 282 ms 16492 KB Output is correct
7 Correct 273 ms 16508 KB Output is correct
8 Correct 257 ms 16472 KB Output is correct
9 Correct 318 ms 16492 KB Output is correct
10 Correct 275 ms 16496 KB Output is correct
11 Correct 288 ms 16256 KB Output is correct
12 Correct 406 ms 16272 KB Output is correct
13 Correct 314 ms 16268 KB Output is correct
14 Correct 308 ms 16288 KB Output is correct
15 Correct 266 ms 16492 KB Output is correct
16 Correct 238 ms 16504 KB Output is correct
17 Correct 284 ms 16252 KB Output is correct
18 Correct 291 ms 16280 KB Output is correct
19 Correct 250 ms 16496 KB Output is correct
20 Correct 261 ms 16260 KB Output is correct
21 Correct 240 ms 17244 KB Output is correct
22 Correct 225 ms 17196 KB Output is correct
23 Correct 201 ms 17108 KB Output is correct
24 Correct 246 ms 17004 KB Output is correct
25 Correct 305 ms 16480 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6380 KB Output is correct
2 Incorrect 38 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 24 ms 6344 KB Output is correct
2 Correct 45 ms 6364 KB Output is correct
3 Partially correct 303 ms 16952 KB Output is partially correct
4 Incorrect 320 ms 17112 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -