oj.uz

Submission #121602

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

long long a, b;
long long sm;

queue<long long> q;
vector<int> temp;

vector<pair<long long, long long> > bfs(long long x){
	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;

		
		temp.clear();
		for(int i = 0; i < (int)adj[u].size(); i++){
			temp.push_back(i);
		}

		for(int i = 0; i < (int)adj[u].size(); i++){
			int x = mt() % adj[u].size();
			int y = mt() % adj[u].size();

			swap(temp[x], temp[y]);
		}
 
		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);
			}
		}

		for(long long i = 0; i < adj[u].size(); i++){
			long long to = adj[u][temp[i]];
			long long j = idx[u][temp[i]];
 
			if(!used[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));

	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:54:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i = 0; i < adj[u].size(); i++){
                        ~~^~~~~~~~~~~~~~~
highway.cpp:56:14: warning: unused variable 'j' [-Wunused-variable]
    long long j = idx[u][i];
              ^
highway.cpp:63: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 7 ms 5108 KB Output is correct
2 Correct 7 ms 4980 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 8 ms 4984 KB Output is correct
5 Correct 7 ms 5024 KB Output is correct
6 Correct 6 ms 5108 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 6 ms 5024 KB Output is correct
9 Correct 6 ms 4980 KB Output is correct
10 Correct 6 ms 5032 KB Output is correct
11 Correct 6 ms 5024 KB Output is correct
12 Correct 6 ms 5036 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 23 ms 6272 KB Output is correct
3 Correct 293 ms 16224 KB Output is correct
4 Correct 318 ms 16228 KB Output is correct
5 Correct 314 ms 16220 KB Output is correct
6 Correct 331 ms 16212 KB Output is correct
7 Correct 248 ms 16236 KB Output is correct
8 Correct 214 ms 16244 KB Output is correct
9 Correct 296 ms 16220 KB Output is correct
10 Correct 302 ms 16220 KB Output is correct
11 Correct 256 ms 16020 KB Output is correct
12 Correct 301 ms 15988 KB Output is correct
13 Correct 385 ms 16104 KB Output is correct
14 Correct 313 ms 15992 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6248 KB Output is correct
2 Correct 50 ms 7404 KB Output is correct
3 Correct 90 ms 8440 KB Output is correct
4 Correct 176 ms 16112 KB Output is correct
5 Correct 198 ms 16096 KB Output is correct
6 Correct 177 ms 16080 KB Output is correct
7 Correct 147 ms 16000 KB Output is correct
8 Correct 185 ms 16008 KB Output is correct
9 Correct 197 ms 15992 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 55 ms 6260 KB Output is correct
3 Correct 206 ms 14212 KB Output is correct
4 Correct 284 ms 16212 KB Output is correct
5 Correct 264 ms 16384 KB Output is correct
6 Correct 324 ms 16208 KB Output is correct
7 Correct 278 ms 16224 KB Output is correct
8 Correct 250 ms 16204 KB Output is correct
9 Correct 270 ms 16240 KB Output is correct
10 Correct 276 ms 16236 KB Output is correct
11 Correct 273 ms 16100 KB Output is correct
12 Correct 299 ms 16012 KB Output is correct
13 Correct 301 ms 16104 KB Output is correct
14 Correct 312 ms 15996 KB Output is correct
15 Correct 262 ms 16224 KB Output is correct
16 Correct 301 ms 16232 KB Output is correct
17 Correct 330 ms 16024 KB Output is correct
18 Correct 364 ms 15996 KB Output is correct
19 Correct 285 ms 16240 KB Output is correct
20 Correct 277 ms 16112 KB Output is correct
21 Correct 263 ms 17812 KB Output is correct
22 Correct 228 ms 17792 KB Output is correct
23 Correct 285 ms 17272 KB Output is correct
24 Correct 253 ms 17296 KB Output is correct
25 Correct 312 ms 16164 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 6300 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 42 ms 6288 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -