oj.uz

Submission #141544

# Submission time Handle Problem Language Result Execution time Memory
141544 2019-08-08T11:23:56 Z Lawliet Highway Tolls (IOI18_highway) C++14
51 / 100
 338 ms 22248 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 );

	//printf("i = %d    %d\n",i,prof[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;
	//printf("oi\n");
	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;

	//printf("---- %lld %lld\n",distA,distB);

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

		//printf("L = %d  R = %d\n",l,r);

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

	//printf("PROF = %d\n",r);

	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:30: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:85: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 8 ms 6652 KB Output is correct
2 Correct 7 ms 6680 KB Output is correct
3 Correct 8 ms 6648 KB Output is correct
4 Correct 8 ms 6672 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 9 ms 6752 KB Output is correct
7 Correct 8 ms 6648 KB Output is correct
8 Correct 8 ms 6756 KB Output is correct
9 Correct 8 ms 6648 KB Output is correct
10 Correct 10 ms 6648 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 8 ms 6760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6776 KB Output is correct
2 Correct 33 ms 7592 KB Output is correct
3 Correct 338 ms 16216 KB Output is correct
4 Correct 289 ms 16012 KB Output is correct
5 Correct 279 ms 16200 KB Output is correct
6 Correct 262 ms 16132 KB Output is correct
7 Correct 272 ms 16364 KB Output is correct
8 Correct 267 ms 16376 KB Output is correct
9 Correct 275 ms 16480 KB Output is correct
10 Correct 274 ms 16144 KB Output is correct
11 Correct 280 ms 17192 KB Output is correct
12 Correct 291 ms 17932 KB Output is correct
13 Correct 298 ms 17148 KB Output is correct
14 Correct 278 ms 17500 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8280 KB Output is correct
2 Correct 48 ms 9984 KB Output is correct
3 Correct 66 ms 11836 KB Output is correct
4 Correct 183 ms 22188 KB Output is correct
5 Correct 203 ms 22172 KB Output is correct
6 Correct 196 ms 22180 KB Output is correct
7 Correct 190 ms 22176 KB Output is correct
8 Correct 191 ms 22168 KB Output is correct
9 Correct 193 ms 22248 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6696 KB Output is correct
2 Correct 31 ms 7720 KB Output is correct
3 Correct 198 ms 14124 KB Output is correct
4 Correct 277 ms 16020 KB Output is correct
5 Correct 255 ms 15892 KB Output is correct
6 Correct 263 ms 16244 KB Output is correct
7 Correct 252 ms 16080 KB Output is correct
8 Correct 268 ms 16088 KB Output is correct
9 Correct 275 ms 16360 KB Output is correct
10 Correct 259 ms 16072 KB Output is correct
11 Correct 293 ms 17232 KB Output is correct
12 Correct 291 ms 17832 KB Output is correct
13 Correct 325 ms 17356 KB Output is correct
14 Correct 301 ms 17996 KB Output is correct
15 Correct 268 ms 16024 KB Output is correct
16 Correct 252 ms 15928 KB Output is correct
17 Correct 293 ms 17748 KB Output is correct
18 Correct 296 ms 17764 KB Output is correct
19 Correct 264 ms 16108 KB Output is correct
20 Correct 285 ms 18404 KB Output is correct
21 Correct 231 ms 17336 KB Output is correct
22 Correct 231 ms 17292 KB Output is correct
23 Correct 247 ms 16768 KB Output is correct
24 Correct 251 ms 17244 KB Output is correct
25 Correct 302 ms 21636 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 7544 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 7396 KB Incorrect
2 Halted 0 ms 0 KB -