oj.uz

Submission #118791

# Submission time Handle Problem Language Result Execution time Memory
118791 2019-06-19T18:13:25 Z Sorting Highway Tolls (IOI18_highway) C++14
51 / 100
 373 ms 262148 KB 
#include <bits/stdc++.h>
//#include "highway.h"

using namespace std;

const int 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;
vector<pair<int, int> > e;
int depth[MAXN];
bool used[MAXN];

long long a, b;
long long sm;

void dfs(int u, int pr = -1, int d = 0){
	depth[u] = d;
	for(int i = 0; i < adj[u].size(); i++){
		int to = adj[u][i], j = idx[u][i];

		if(to == pr || used[to]){
			continue;
		}

		e.push_back({d + 1, j});
		dfs(to, u, d + 1);
	}
}

int f(int u, const vector<int> &V, const vector<int> &U){
	e.clear();
	dfs(u);

	if(e.empty()){
		return u;
	}

	sort(e.begin(), e.end());

	int l = 0, r = (int)e.size() - 1;

	for(int i = 0; i < m; i++){
		w[i] = 0;
	}
	for(int i = l; i <= r; i++){
		w[e[i].second] = true;
	}

	if(ask(w) == sm){
		return u;
	}

	while(l != r){
		int mid = (l + r) / 2;

		for(int i = 0; i < m; i++){
			w[i] = 0;
		}
		for(int i = mid + 1; i <= r; i++){
			w[e[i].second] = true;
		}

		long long score = ask(w);
		score -= sm;

		if(score){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}

	int x = V[e[l].second], y = U[e[l].second];

	if(depth[x] < depth[y]){
		swap(x, y);
	}

	return x;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	n = N;
	m = U.size();

	for(int 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;

	int l = 0, r = m - 1;

	while(l != r){
		int mid = (l + r) / 2;

		for(int i = 0; i < m; i++){
			w[i] = 0; 
		}
		for(int i = mid + 1; i <= r; i++){
			w[i] = 1;
		}

		long long score = ask(w);
		score -= sm;

		if(score){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}

	int x, y;

	used[V[l]] = true;
	x = f(U[l], V, U);

	used[V[l]] = false;
	used[U[l]] = true;
	y = f(V[l], V, U);

	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 dfs(int, int, int)':
highway.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++){
                 ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5116 KB Output is correct
2 Correct 7 ms 5116 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 17 ms 5032 KB Output is correct
5 Correct 6 ms 5024 KB Output is correct
6 Correct 7 ms 5028 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5012 KB Output is correct
10 Correct 6 ms 5032 KB Output is correct
11 Correct 6 ms 4984 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 31 ms 6124 KB Output is correct
3 Correct 236 ms 14056 KB Output is correct
4 Correct 254 ms 14152 KB Output is correct
5 Correct 229 ms 14044 KB Output is correct
6 Correct 224 ms 14164 KB Output is correct
7 Correct 243 ms 14112 KB Output is correct
8 Correct 256 ms 14060 KB Output is correct
9 Correct 248 ms 14052 KB Output is correct
10 Correct 252 ms 14040 KB Output is correct
11 Correct 268 ms 15476 KB Output is correct
12 Correct 254 ms 16464 KB Output is correct
13 Correct 240 ms 15972 KB Output is correct
14 Correct 238 ms 16284 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6904 KB Output is correct
2 Correct 59 ms 8164 KB Output is correct
3 Correct 66 ms 10448 KB Output is correct
4 Correct 194 ms 18112 KB Output is correct
5 Correct 172 ms 18564 KB Output is correct
6 Correct 189 ms 20552 KB Output is correct
7 Correct 176 ms 21600 KB Output is correct
8 Correct 212 ms 18860 KB Output is correct
9 Correct 174 ms 19980 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 23 ms 6124 KB Output is correct
3 Correct 195 ms 12352 KB Output is correct
4 Correct 228 ms 14044 KB Output is correct
5 Correct 246 ms 14160 KB Output is correct
6 Correct 242 ms 14036 KB Output is correct
7 Correct 249 ms 14092 KB Output is correct
8 Correct 231 ms 14048 KB Output is correct
9 Correct 261 ms 13676 KB Output is correct
10 Correct 250 ms 14048 KB Output is correct
11 Correct 238 ms 15608 KB Output is correct
12 Correct 244 ms 16536 KB Output is correct
13 Correct 271 ms 15560 KB Output is correct
14 Correct 242 ms 15904 KB Output is correct
15 Correct 259 ms 14048 KB Output is correct
16 Correct 212 ms 14032 KB Output is correct
17 Correct 259 ms 16000 KB Output is correct
18 Correct 258 ms 16208 KB Output is correct
19 Correct 267 ms 14052 KB Output is correct
20 Correct 322 ms 17028 KB Output is correct
21 Correct 198 ms 14556 KB Output is correct
22 Correct 216 ms 14552 KB Output is correct
23 Correct 232 ms 14316 KB Output is correct
24 Correct 220 ms 14752 KB Output is correct
25 Correct 251 ms 20928 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 373 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 351 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -