oj.uz

Submission #121627

# Submission time Handle Problem Language Result Execution time Memory
121627 2019-06-26T21:00:27 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 368 ms 22004 KB 
#include <bits/stdc++.h>
#include "highway.h"
 
using namespace std;
 
const long long MAXN = 2e5 + 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 11 ms 9720 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 11 ms 9724 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 10 ms 9724 KB Output is correct
6 Correct 11 ms 9724 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 10 ms 9720 KB Output is correct
9 Correct 11 ms 9720 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 11 ms 9720 KB Output is correct
12 Correct 10 ms 9720 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9884 KB Output is correct
2 Correct 33 ms 10984 KB Output is correct
3 Correct 257 ms 21184 KB Output is correct
4 Correct 264 ms 21200 KB Output is correct
5 Correct 294 ms 21204 KB Output is correct
6 Correct 300 ms 21164 KB Output is correct
7 Correct 276 ms 21212 KB Output is correct
8 Correct 246 ms 21192 KB Output is correct
9 Correct 269 ms 21196 KB Output is correct
10 Correct 265 ms 21212 KB Output is correct
11 Correct 284 ms 21096 KB Output is correct
12 Correct 316 ms 20956 KB Output is correct
13 Correct 309 ms 20968 KB Output is correct
14 Correct 316 ms 20956 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10980 KB Output is correct
2 Correct 58 ms 12224 KB Output is correct
3 Correct 69 ms 13308 KB Output is correct
4 Correct 187 ms 21064 KB Output is correct
5 Correct 209 ms 20936 KB Output is correct
6 Correct 207 ms 20956 KB Output is correct
7 Correct 213 ms 20948 KB Output is correct
8 Correct 212 ms 21056 KB Output is correct
9 Correct 232 ms 20944 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 47 ms 11008 KB Output is correct
3 Correct 197 ms 19108 KB Output is correct
4 Correct 276 ms 21188 KB Output is correct
5 Correct 242 ms 21188 KB Output is correct
6 Correct 247 ms 21172 KB Output is correct
7 Correct 254 ms 21288 KB Output is correct
8 Correct 254 ms 21172 KB Output is correct
9 Correct 269 ms 21176 KB Output is correct
10 Correct 296 ms 21200 KB Output is correct
11 Correct 329 ms 20960 KB Output is correct
12 Correct 279 ms 20968 KB Output is correct
13 Correct 304 ms 20964 KB Output is correct
14 Correct 314 ms 20956 KB Output is correct
15 Correct 368 ms 21200 KB Output is correct
16 Correct 274 ms 21220 KB Output is correct
17 Correct 298 ms 20964 KB Output is correct
18 Correct 326 ms 20984 KB Output is correct
19 Correct 250 ms 21184 KB Output is correct
20 Correct 317 ms 20952 KB Output is correct
21 Correct 189 ms 21880 KB Output is correct
22 Correct 196 ms 22004 KB Output is correct
23 Correct 251 ms 21784 KB Output is correct
24 Correct 254 ms 21680 KB Output is correct
25 Correct 315 ms 21052 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11028 KB Output is correct
2 Incorrect 40 ms 11064 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 36 ms 11036 KB Output is correct
2 Correct 28 ms 11060 KB Output is correct
3 Partially correct 316 ms 21844 KB Output is partially correct
4 Incorrect 327 ms 21828 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -