oj.uz

Submission #125505

# Submission time Handle Problem Language Result Execution time Memory
125505 2019-07-05T13:54:31 Z TuGSGeReL Highway Tolls (IOI18_highway) C++17
51 / 100
 373 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>;
 
ll mn;
int 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();
	
	for (int i = 0; i < m; i++)
		check.pub(0);
	
	dfs(0, -1);
	mn = ask(check);
	int l = 1, r = arr.size() - 1;

	for (int i = 0; i < m; i++)
		check[i] = 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;
	
	for (int i = 0; i < m; i++)
		check[i] = 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:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++)
                  ~~^~~~~~~~~~

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 2428 KB Output is correct
5 Correct 4 ms 2344 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2340 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2424 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 23 ms 3112 KB Output is correct
3 Correct 204 ms 9032 KB Output is correct
4 Correct 219 ms 9040 KB Output is correct
5 Correct 187 ms 8940 KB Output is correct
6 Correct 227 ms 8964 KB Output is correct
7 Correct 204 ms 9028 KB Output is correct
8 Correct 203 ms 9044 KB Output is correct
9 Correct 226 ms 8944 KB Output is correct
10 Correct 197 ms 8968 KB Output is correct
11 Correct 234 ms 10180 KB Output is correct
12 Correct 228 ms 10908 KB Output is correct
13 Correct 237 ms 10288 KB Output is correct
14 Correct 222 ms 10216 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3884 KB Output is correct
2 Correct 59 ms 5408 KB Output is correct
3 Correct 59 ms 6824 KB Output is correct
4 Correct 162 ms 15256 KB Output is correct
5 Correct 170 ms 15268 KB Output is correct
6 Correct 154 ms 15256 KB Output is correct
7 Correct 162 ms 15296 KB Output is correct
8 Correct 173 ms 15248 KB Output is correct
9 Correct 158 ms 15256 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 45 ms 3184 KB Output is correct
3 Correct 164 ms 7732 KB Output is correct
4 Correct 204 ms 9032 KB Output is correct
5 Correct 204 ms 8944 KB Output is correct
6 Correct 215 ms 8936 KB Output is correct
7 Correct 199 ms 9036 KB Output is correct
8 Correct 197 ms 9032 KB Output is correct
9 Correct 219 ms 9036 KB Output is correct
10 Correct 180 ms 9036 KB Output is correct
11 Correct 217 ms 9476 KB Output is correct
12 Correct 215 ms 10956 KB Output is correct
13 Correct 229 ms 10400 KB Output is correct
14 Correct 216 ms 10712 KB Output is correct
15 Correct 188 ms 9044 KB Output is correct
16 Correct 208 ms 9032 KB Output is correct
17 Correct 213 ms 10576 KB Output is correct
18 Correct 206 ms 10544 KB Output is correct
19 Correct 225 ms 9032 KB Output is correct
20 Correct 211 ms 11460 KB Output is correct
21 Correct 174 ms 9408 KB Output is correct
22 Correct 173 ms 9440 KB Output is correct
23 Correct 161 ms 9272 KB Output is correct
24 Correct 195 ms 9796 KB Output is correct
25 Correct 218 ms 14552 KB Output is correct

Subtask #5
0 / 18.0

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