oj.uz

Submission #139333

# Submission time Handle Problem Language Result Execution time Memory
139333 2019-07-31T14:54:46 Z Lawliet Highway Tolls (IOI18_highway) C++14
5 / 100
 40 ms 660 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 degree[MAX];

bool inPath[MAX];

pii edges[MAX];

vector<int> question;

/*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[ g ] = {i , j};
	}

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

	lli dist = ask( question );

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

		lli aux = ask( question );

		if(dist != aux) inPath[ g ] = true;

		question[ g ] = 0;
	}

	for(int g = 0 ; g < N - 1 ; g++)
	{
		if(inPath[ g ])
		{
			degree[ edges[g].first ]++;
			degree[ edges[g].second ]++; 
		}
	}

	vector<int> ans;

	for(int g = 0 ; g < N ; g++)
		if(degree[g] == 1) ans.push_back( g );

	answer(ans[0] , ans[1]);
}

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

	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 , 0 , 0);
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 3 ms 328 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 328 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 248 KB Output is correct
11 Correct 3 ms 412 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 348 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 660 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 376 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 652 KB Incorrect
2 Halted 0 ms 0 KB -