oj.uz

Submission #119284

# Submission time Handle Problem Language Result Execution time Memory
119284 2019-06-20T22:28:53 Z joseacaz Highway Tolls (IOI18_highway) C++17
51 / 100
 232 ms 18048 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define MAXN 90005
#define MAXM 130005

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N, M, pathLength, S, T;
ll A, B;
vector < int > U, V, Q;
vector < pii > Graph[MAXN];
vector < pair < int, pii > > nodes;

bool bin ( int x )
{
	fill ( Q.begin(), Q.begin() + x + 1, 1 );
	fill ( Q.begin() + x + 1, Q.end(), 0 );

	ll tmp = ask ( Q );
	if ( tmp != A * pathLength )
		return true;
	return false;
}

bool bin2 ( int x )
{
	fill ( Q.begin(), Q.end(), 1 );
	for ( int i = x; i < nodes.size(); i++ )
		Q[nodes[i].second.first] = 0;

	ll tmp = ask ( Q );
	return (tmp == B * pathLength);
}

void dfs ( int node, int parent = -1, int depth = 0 )
{
	for ( auto i : Graph[node] )
		if ( i.first != parent )
			dfs ( i.first, node, depth + 1 ), nodes.push_back ( {depth, {i.second, i.first}} );
}

int solve ( int node )
{
	sort ( nodes.begin(), nodes.end() );

	int s = 0, e = nodes.size(), mid, val, ans;
	while ( s <= e )
	{
		mid = (s + e) / 2;
		val = bin2 ( mid );

		if ( val )
			ans = mid, e = mid - 1;
		else
			s = mid + 1;
	}

	if ( ans == 0 )
		return node;
	return nodes[ans - 1].second.second;
}

void find_pair ( int _N, vector<int> _U, vector<int> _V, int _A, int _B )
{
	N = _N;
	M = _U.size();
	A = _A;
	B = _B;
	swap ( U, _U );
	swap ( V, _V );
	for ( int i = 0; i < M; i++ )
	{
		Graph[U[i]].push_back ( {V[i], i} );
		Graph[V[i]].push_back ( {U[i], i} );
	}
	Q.resize ( M );

	if ( M == N - 1 )
	{
		//Graph is a tree, 51 points
		for ( auto &i : Q )
			i = 0;
		pathLength = ask ( Q ) / A;

		int s = 0, e = M - 1, mid, val, edge;
		while ( s <= e )
		{
			mid = (s + e) / 2;
			val = bin ( mid );

			if ( val )
				edge = mid, e = mid - 1;
			else
				s = mid + 1;
		}

		nodes.clear();
		dfs ( U[edge], V[edge] );
		S = solve ( U[edge] );

		nodes.clear();
		dfs ( V[edge], U[edge] );
		T = solve ( V[edge] );

		answer ( S, T );
	}
}

Compilation message

highway.cpp: In function 'bool bin2(int)':
highway.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = x; i < nodes.size(); i++ )
                   ~~^~~~~~~~~~~~~~
highway.cpp: In function 'int solve(int)':
highway.cpp:62:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return nodes[ans - 1].second.second;
               ~~~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:100:24: warning: 'edge' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dfs ( U[edge], V[edge] );
                        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2432 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2344 KB Output is correct
7 Correct 4 ms 2420 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2340 KB Output is correct
11 Correct 4 ms 2428 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 25 ms 3192 KB Output is correct
3 Correct 221 ms 9232 KB Output is correct
4 Correct 211 ms 9168 KB Output is correct
5 Correct 199 ms 9180 KB Output is correct
6 Correct 221 ms 9240 KB Output is correct
7 Correct 195 ms 9216 KB Output is correct
8 Correct 222 ms 9160 KB Output is correct
9 Correct 204 ms 9240 KB Output is correct
10 Correct 208 ms 9168 KB Output is correct
11 Correct 232 ms 9708 KB Output is correct
12 Correct 210 ms 11872 KB Output is correct
13 Correct 196 ms 11116 KB Output is correct
14 Correct 219 ms 11248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4084 KB Output is correct
2 Correct 43 ms 5568 KB Output is correct
3 Correct 55 ms 7300 KB Output is correct
4 Correct 176 ms 13908 KB Output is correct
5 Correct 166 ms 14000 KB Output is correct
6 Correct 173 ms 16572 KB Output is correct
7 Correct 146 ms 18048 KB Output is correct
8 Correct 168 ms 14864 KB Output is correct
9 Correct 182 ms 15940 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 26 ms 3148 KB Output is correct
3 Correct 146 ms 8100 KB Output is correct
4 Correct 199 ms 9232 KB Output is correct
5 Correct 184 ms 9208 KB Output is correct
6 Correct 196 ms 9244 KB Output is correct
7 Correct 189 ms 9236 KB Output is correct
8 Correct 227 ms 9216 KB Output is correct
9 Correct 200 ms 9224 KB Output is correct
10 Correct 221 ms 9232 KB Output is correct
11 Correct 213 ms 10728 KB Output is correct
12 Correct 204 ms 11824 KB Output is correct
13 Correct 230 ms 11380 KB Output is correct
14 Correct 213 ms 10472 KB Output is correct
15 Correct 190 ms 9188 KB Output is correct
16 Correct 231 ms 9192 KB Output is correct
17 Correct 225 ms 10856 KB Output is correct
18 Correct 224 ms 11536 KB Output is correct
19 Correct 188 ms 9232 KB Output is correct
20 Correct 226 ms 12308 KB Output is correct
21 Correct 150 ms 10048 KB Output is correct
22 Correct 176 ms 9992 KB Output is correct
23 Correct 151 ms 8880 KB Output is correct
24 Correct 188 ms 9456 KB Output is correct
25 Correct 221 ms 17088 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2964 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 2932 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -