oj.uz

Submission #118767

# Submission time Handle Problem Language Result Execution time Memory
118767 2019-06-19T16:52:17 Z Sorting Highway Tolls (IOI18_highway) C++14
7 / 100
 370 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, vector<int> &V, 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;

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

	if(l > r){
		return u;
	}

	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5024 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 6 ms 4976 KB Output is correct
5 Incorrect 6 ms 4968 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5104 KB Output is correct
2 Correct 21 ms 6032 KB Output is correct
3 Correct 255 ms 14152 KB Output is correct
4 Correct 230 ms 14148 KB Output is correct
5 Correct 208 ms 14104 KB Output is correct
6 Correct 247 ms 14048 KB Output is correct
7 Correct 238 ms 14116 KB Output is correct
8 Correct 223 ms 14092 KB Output is correct
9 Correct 243 ms 14176 KB Output is correct
10 Correct 234 ms 14056 KB Output is correct
11 Correct 283 ms 15444 KB Output is correct
12 Correct 253 ms 16476 KB Output is correct
13 Correct 243 ms 16024 KB Output is correct
14 Correct 249 ms 16284 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5028 KB Output is correct
2 Correct 32 ms 6124 KB Output is correct
3 Correct 183 ms 12452 KB Output is correct
4 Correct 234 ms 14044 KB Output is correct
5 Incorrect 245 ms 14164 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 370 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 345 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -