oj.uz

Submission #141546

# Submission time Handle Problem Language Result Execution time Memory
141546 2019-08-08T11:25:00 Z Lawliet Highway Tolls (IOI18_highway) C++14
51 / 100
 324 ms 22344 KB 
#include <bits/stdc++.h>
#include "highway.h"
 
#define MAX 90010
 
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
 
int N, A, B;
 
int prof[MAX];
int paiEdge[MAX];

lli distA;
lli distB;
 
vector<int> grafo[MAX];
vector<int> indEdge[MAX];
vector<int> distNode[MAX];

vector<pii> searchSpace;

void DFS(int i, int p)
{
	distNode[ prof[i] ].push_back( i );

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];
		int ind = indEdge[i][g];

		if(prox == p) continue;

		paiEdge[ prox ] = ind;
		prof[ prox ] = prof[ i ] + 1;

		DFS(prox , i);
	}
}

void initDFS()
{
	for(int g = 0 ; g <= N ; g++)
		distNode[ g ].clear();
}

bool test(int l, int r)
{
	vector<int> query(N - 1 , 0);

	for(int g = l ; g <= r ; g++)
	{
		int cur = searchSpace[ g ].second;

		query[ cur ] = 1;
	}

	lli aux = ask( query );

	return aux != distA;
}

bool test(int k)
{
	vector<int> query(N - 1 , 0);

	for(int g = 1 ; g < N ; g++)
		if(prof[g] <= k) query[ paiEdge[g] ] = 1;

	lli aux = ask( query );

	return aux == distB;
}

int find(int root, int d)
{
	initDFS(); prof[ root ] = 0;
	DFS(root , root);

	searchSpace.clear();

	for(int g = 0 ; g < distNode[ d ].size() ; g++)
	{
		int prox = distNode[d][g];
		searchSpace.push_back({ prox , paiEdge[ prox ] });
	}

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

	while(l < r)
	{
		int m = (l + r)/2;

		if(test(l , m)) r = m;
		else l = m + 1;
	}

	return searchSpace[ l ].first;
}
 
void find_pair(int n, vector<int> U, vector<int> V, int a, int b)
{
	N = n; A = a; B = b;
 
	for(int g = 0 ; g < N - 1 ; g++)
	{
		int i = U[g];
		int j = V[g];

		grafo[ i ].push_back( j );
		grafo[ j ].push_back( i );

		indEdge[ i ].push_back( g );
		indEdge[ j ].push_back( g );
	}

	vector<int> nullVector(N - 1 , 0);

	distA = ask( nullVector );
	distB = distA/A; distB *= B;

	DFS(0 , 0);

	int l = 0, r = n - 1;

	while(l < r)
	{
		int m = (l + r)/2;

		if(test(m)) r = m;
		else l = m + 1;
	}

	int S = find(0 , r);
	int T = find(S , distA/A);

	answer(S , T);
}

Compilation message

highway.cpp: In function 'void DFS(int, int)':
highway.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'int find(int, int)':
highway.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < distNode[ d ].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6648 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 8 ms 6676 KB Output is correct
4 Correct 8 ms 6648 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6648 KB Output is correct
7 Correct 7 ms 6676 KB Output is correct
8 Correct 8 ms 6648 KB Output is correct
9 Correct 7 ms 6648 KB Output is correct
10 Correct 9 ms 6672 KB Output is correct
11 Correct 8 ms 6764 KB Output is correct
12 Correct 7 ms 6648 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6748 KB Output is correct
2 Correct 31 ms 7704 KB Output is correct
3 Correct 267 ms 16200 KB Output is correct
4 Correct 262 ms 16072 KB Output is correct
5 Correct 305 ms 16296 KB Output is correct
6 Correct 273 ms 16008 KB Output is correct
7 Correct 251 ms 16308 KB Output is correct
8 Correct 276 ms 16376 KB Output is correct
9 Correct 268 ms 16428 KB Output is correct
10 Correct 277 ms 16220 KB Output is correct
11 Correct 291 ms 17284 KB Output is correct
12 Correct 297 ms 17940 KB Output is correct
13 Correct 294 ms 17296 KB Output is correct
14 Correct 295 ms 17576 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8360 KB Output is correct
2 Correct 51 ms 10016 KB Output is correct
3 Correct 69 ms 11768 KB Output is correct
4 Correct 195 ms 22344 KB Output is correct
5 Correct 182 ms 22176 KB Output is correct
6 Correct 190 ms 22260 KB Output is correct
7 Correct 201 ms 22184 KB Output is correct
8 Correct 189 ms 22232 KB Output is correct
9 Correct 195 ms 22228 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6776 KB Output is correct
2 Correct 31 ms 7720 KB Output is correct
3 Correct 209 ms 14124 KB Output is correct
4 Correct 258 ms 16092 KB Output is correct
5 Correct 259 ms 15864 KB Output is correct
6 Correct 324 ms 16200 KB Output is correct
7 Correct 240 ms 16168 KB Output is correct
8 Correct 282 ms 16184 KB Output is correct
9 Correct 272 ms 16252 KB Output is correct
10 Correct 281 ms 16092 KB Output is correct
11 Correct 302 ms 17132 KB Output is correct
12 Correct 291 ms 17824 KB Output is correct
13 Correct 302 ms 17336 KB Output is correct
14 Correct 298 ms 17884 KB Output is correct
15 Correct 269 ms 15984 KB Output is correct
16 Correct 254 ms 15980 KB Output is correct
17 Correct 289 ms 17584 KB Output is correct
18 Correct 299 ms 17864 KB Output is correct
19 Correct 264 ms 16036 KB Output is correct
20 Correct 297 ms 18368 KB Output is correct
21 Correct 225 ms 17340 KB Output is correct
22 Correct 216 ms 17332 KB Output is correct
23 Correct 240 ms 16848 KB Output is correct
24 Correct 238 ms 17308 KB Output is correct
25 Correct 318 ms 21664 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 7416 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 7384 KB Incorrect
2 Halted 0 ms 0 KB -