oj.uz

Submission #125498

# Submission time Handle Problem Language Result Execution time Memory
125498 2019-07-05T13:41:45 Z TuGSGeReL Highway Tolls (IOI18_highway) C++17
0 / 100
 374 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

int mn, m, a, b, par[90000], num[90000];
vector <pii> edg[90000];
vector <int> check, arr;

void dfs(int u, int pr)
{
	arr.pub(u);
	
	for (auto x : edg[u])
	{
		if ( x.ff != pr )
		{
			par[x.ff] = u;
			num[x.ff] = x.ss;
			dfs(x.ff, u);
		}
	}
}

bool shal(int k, int p)
{
	for (int i = k; i <= p; i++)
		check[num[arr[i]]] = 0;
	
	if ( ask(check) > mn )
		return 1;
	
	return 0;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	for (int i = 0; i < U.size(); i++)
	{
		edg[U[i]].pub(mp(V[i], i));
		edg[V[i]].pub(mp(U[i], i));
	}
	
	m = U.size();
	check.resize(m);
	dfs(0, -1);
	mn = ask(check);
	int l = 1, r = arr.size() - 1;
	check.resize(m, 1);
	
	while (l != r)
	{
		int mid = (l + r) / 2;
		
		if ( shal(l, mid) )
			l = mid + 1;
		
		else
		{
			r = mid;
			
			for ( int i = l; i <= mid; i++)
				check[num[arr[i]]] = 1;
		}
	}
	
	a = arr[l];
	arr.clear();
	dfs(a, -1);
	l = 1, r = arr.size() - 1;
	check.resize(m, 1);
	
	while (l != r)
	{
		int mid = (l + r) / 2;
		
		if ( shal(l, mid) )
			l = mid + 1;
		
		else
		{
			r = mid;
			
			for ( int i = l; i <= mid; i++)
				check[num[arr[i]]] = 1;
		}
	}
	
	b = arr[l];
	answer(a, b);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++)
                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2424 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 Correct 23 ms 3832 KB Output is correct
2 Correct 27 ms 5276 KB Output is correct
3 Incorrect 62 ms 6700 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2552 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 Runtime error 374 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 340 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -