oj.uz

Submission #121623

# Submission time Handle Problem Language Result Execution time Memory
121623 2019-06-26T20:55:05 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 380 ms 17208 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;
	}
 
	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 5036 KB Output is correct
2 Correct 6 ms 5032 KB Output is correct
3 Correct 6 ms 5032 KB Output is correct
4 Correct 6 ms 5036 KB Output is correct
5 Correct 6 ms 5032 KB Output is correct
6 Correct 6 ms 5028 KB Output is correct
7 Correct 6 ms 5000 KB Output is correct
8 Correct 6 ms 5116 KB Output is correct
9 Correct 6 ms 5032 KB Output is correct
10 Correct 6 ms 5036 KB Output is correct
11 Correct 7 ms 5036 KB Output is correct
12 Correct 6 ms 5028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5108 KB Output is correct
2 Correct 35 ms 6308 KB Output is correct
3 Correct 309 ms 16504 KB Output is correct
4 Correct 291 ms 16488 KB Output is correct
5 Correct 261 ms 16484 KB Output is correct
6 Correct 338 ms 16488 KB Output is correct
7 Correct 265 ms 16584 KB Output is correct
8 Correct 286 ms 16492 KB Output is correct
9 Correct 256 ms 16500 KB Output is correct
10 Correct 244 ms 16492 KB Output is correct
11 Correct 298 ms 16276 KB Output is correct
12 Correct 261 ms 16264 KB Output is correct
13 Correct 288 ms 16276 KB Output is correct
14 Correct 300 ms 16268 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6252 KB Output is correct
2 Correct 50 ms 7544 KB Output is correct
3 Correct 66 ms 8564 KB Output is correct
4 Correct 208 ms 16324 KB Output is correct
5 Correct 203 ms 16272 KB Output is correct
6 Correct 197 ms 16288 KB Output is correct
7 Correct 219 ms 16260 KB Output is correct
8 Correct 253 ms 16264 KB Output is correct
9 Correct 188 ms 16244 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 28 ms 6316 KB Output is correct
3 Correct 192 ms 14416 KB Output is correct
4 Correct 268 ms 16504 KB Output is correct
5 Correct 267 ms 16476 KB Output is correct
6 Correct 254 ms 16468 KB Output is correct
7 Correct 223 ms 16476 KB Output is correct
8 Correct 313 ms 16476 KB Output is correct
9 Correct 268 ms 16492 KB Output is correct
10 Correct 310 ms 16492 KB Output is correct
11 Correct 309 ms 16268 KB Output is correct
12 Correct 294 ms 16272 KB Output is correct
13 Correct 341 ms 16272 KB Output is correct
14 Correct 380 ms 16396 KB Output is correct
15 Correct 256 ms 16488 KB Output is correct
16 Correct 275 ms 16492 KB Output is correct
17 Correct 301 ms 16280 KB Output is correct
18 Correct 270 ms 16276 KB Output is correct
19 Correct 275 ms 16504 KB Output is correct
20 Correct 245 ms 16344 KB Output is correct
21 Correct 207 ms 17208 KB Output is correct
22 Correct 213 ms 17184 KB Output is correct
23 Correct 220 ms 17100 KB Output is correct
24 Correct 280 ms 17004 KB Output is correct
25 Correct 320 ms 16372 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6336 KB Output is correct
2 Incorrect 39 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 29 ms 6344 KB Output is correct
2 Correct 36 ms 6500 KB Output is correct
3 Partially correct 288 ms 16972 KB Output is partially correct
4 Incorrect 339 ms 17120 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -