oj.uz

Submission #139367

# Submission time Handle Problem Language Result Execution time Memory
139367 2019-07-31T15:20:08 Z Lawliet Highway Tolls (IOI18_highway) C++14
0 / 100
 38 ms 2436 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 v[MAX];

vector<int> indEdge;

map<pii,int> edges;

/*int ask(vector<int> p)
{
	for(int g = 0 ; g < N - 1 ; g++)
		printf("%d ",p[g]);

	int a;
	scanf("%d",&a);

	return a;
}

void answer(int i, int j)
{
	printf("========= %d %d\n",i,j);
}*/

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

		edges[ {i , j} ] = g;
		edges[ {j , i} ] = g;
	}

	for(int g = 1 ; g < N ; g++)
		indEdge.push_back( edges[{g , g - 1}] );

	vector<int> question;

	for(int g = 0 ; g < n - 1 ; g++)
		question.push_back( 0 );

	lli distA = ask( question );

	int qtdEdges = distA/A;

	lli distB = qtdEdges*B;

	int l = 0, r = n - 2;

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

		for(int g = 0 ; g < n - 1 ; g++)
			question[ g ] = 0;

		for(int g = l ; g <= m ; g++)
			question[ indEdge[g] ] = 1;

		lli aux = ask( question );

		if(aux == distA) l = m + 1;
		else if(aux == distB) r = m;
		else
		{
			int other = aux - distA;

			int qtdOther = other/(B - A);

			int midNode = v[ m + 1 ];

			//printf("other = %d     %d       %d         m = %d\n",other,qtdOther,qtdEdges,m);

			answer(v[ (m + 1) - qtdOther ] , v[ qtdEdges + qtdOther - m - 1 ]);

			//printf("ACHEI %d %d\n",(m + 1) - qtdOther,(m + 1) + qtdEdges - qtdOther);
			break;
		}
	}

	//printf("oii %d %d\n",l,l+ 1);
	answer(l , l + 1);

}

/*int main()
{
	int nn, aa, bb;
	scanf("%d %d %d",&nn,&aa,&bb);

	vector<int> uu(nn), vv(nn);

	for(int g = 0 ; g < nn - 1 ; g++)
		scanf("%d %d",&uu[g],&vv[g]);

	find_pair(nn , uu , vv , aa , bb);
}*/

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:83:8: warning: unused variable 'midNode' [-Wunused-variable]
    int midNode = v[ m + 1 ];
        ^~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 2436 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 2416 KB Incorrect
2 Halted 0 ms 0 KB -