oj.uz

Submission #121488

# Submission time Handle Problem Language Result Execution time Memory
121488 2019-06-26T14:37:11 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 311 ms 16716 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();
 
long long n, m;
vector<int> adj[MAXN], idx[MAXN], w;
bool used[MAXN];

long long a, b;
long long sm;
 
vector<pair<long long, long long> > bfs(long long x){
	queue<long long> q;
 
	for(long long i = 0; i < n; i++){
		used[i] = false;
	}
 
	q.push(x);
	
	vector<pair<long long, long long> > v;
 
	while(!q.empty()){
		long long u = q.front();
		q.pop();
 
		if(used[u]){
			continue;
		}
		used[u] = true;
 
		for(long long i = 0; i < adj[u].size(); i++){
			long long to = adj[u][i];
			long long j = idx[u][i];
 
			if(!used[to]){
				q.push(to);
				v.push_back({j, to});
			}
		}
	}
 
	return v;
}

long long away(int x, const vector<int> &U, const vector<int> &V){
	vector<pair<long long, long long> > v = bfs(x);
 
	while((long long)v.size() != m);

	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));

	while(N <= 10);

	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(U[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 'std::vector<std::pair<long long int, long long int> > bfs(long long int)':
highway.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i = 0; i < adj[u].size(); i++){
                        ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5152 KB Output is correct
2 Correct 6 ms 4968 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5024 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 6 ms 5028 KB Output is correct
9 Correct 6 ms 4988 KB Output is correct
10 Correct 6 ms 4928 KB Output is correct
11 Correct 6 ms 5024 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5100 KB Output is correct
2 Correct 21 ms 6296 KB Output is correct
3 Correct 219 ms 16184 KB Output is correct
4 Correct 280 ms 16196 KB Output is correct
5 Correct 221 ms 16184 KB Output is correct
6 Correct 230 ms 16192 KB Output is correct
7 Correct 262 ms 16200 KB Output is correct
8 Correct 252 ms 16188 KB Output is correct
9 Correct 249 ms 16212 KB Output is correct
10 Correct 274 ms 16180 KB Output is correct
11 Correct 231 ms 16000 KB Output is correct
12 Correct 260 ms 16104 KB Output is correct
13 Correct 287 ms 16028 KB Output is correct
14 Correct 291 ms 15996 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6236 KB Output is correct
2 Correct 27 ms 7492 KB Output is correct
3 Correct 76 ms 8532 KB Output is correct
4 Correct 173 ms 15992 KB Output is correct
5 Correct 144 ms 16004 KB Output is correct
6 Correct 184 ms 16028 KB Output is correct
7 Correct 165 ms 15988 KB Output is correct
8 Correct 190 ms 16008 KB Output is correct
9 Correct 170 ms 16076 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 24 ms 6260 KB Output is correct
3 Correct 159 ms 14168 KB Output is correct
4 Correct 264 ms 16184 KB Output is correct
5 Correct 232 ms 16184 KB Output is correct
6 Correct 254 ms 16200 KB Output is correct
7 Correct 267 ms 16208 KB Output is correct
8 Correct 264 ms 16200 KB Output is correct
9 Correct 264 ms 16300 KB Output is correct
10 Correct 220 ms 16244 KB Output is correct
11 Correct 279 ms 15992 KB Output is correct
12 Correct 269 ms 15992 KB Output is correct
13 Correct 241 ms 15996 KB Output is correct
14 Correct 242 ms 16072 KB Output is correct
15 Correct 234 ms 16188 KB Output is correct
16 Correct 185 ms 16188 KB Output is correct
17 Correct 250 ms 15992 KB Output is correct
18 Correct 222 ms 16120 KB Output is correct
19 Correct 231 ms 16192 KB Output is correct
20 Correct 238 ms 15988 KB Output is correct
21 Correct 214 ms 16700 KB Output is correct
22 Correct 211 ms 16700 KB Output is correct
23 Correct 213 ms 16716 KB Output is correct
24 Correct 258 ms 16656 KB Output is correct
25 Correct 311 ms 16080 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6336 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 6296 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -