oj.uz

Submission #295155

# Submission time Handle Problem Language Result Execution time Memory
295155 2020-09-09T13:53:39 Z Kastanda Highway Tolls (IOI18_highway) C++11
100 / 100
 812 ms 12812 KB 
// M
#include<bits/stdc++.h>
#include "highway.h"
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 90004, TOF = 31000;
int n, m, ca, cb, dist, root, H[N];
ll MnCost;
vector < int > alwaysMarked;
vector < pair < int , int > > Adj[N];
inline ll Ask(vector < int > vec)
{
	vector < int > TMp(m, 0);
	for (int i : vec)
		TMp[i] = 1;
	return ask(TMp);
}
inline bool HasImpact(vector < int > vec)
{
	return (Ask(vec) > MnCost);
}
inline vector < int > MarkAll(vector < int > vec)
{
	vector < int > TMp(m, 0), ret;
	for (int i : vec)
		for (auto e : Adj[i])
			TMp[e.second] = 1;
	for (int i : alwaysMarked)
		for (auto e : Adj[i])
			TMp[e.second] = 1;
	for (int i = 0; i < m; i ++)
		if (TMp[i])
			ret.pb(i);
	return ret;
}

void find_pair(int _n, vector < int > _U, vector < int > _V, int _A, int _B)
{
	n = _n;
	m = (int)_U.size();
	for (int i = 0; i < m; i ++)
	{
		Adj[_U[i]].pb({_V[i], i});
		Adj[_V[i]].pb({_U[i], i});
	}
	ca = _A; cb = _B;

	MnCost = Ask(vector < int > {});
	dist = MnCost / ca;

	auto GenerateVec = [](int l, int r){
		vector < int > vec;
		for (int i = l; i < r; i ++)
			vec.pb(i);
		return vec;
	};

  int saved = 0;
	int le = 0, ri = n, md;
	if (n > TOF && HasImpact(MarkAll(GenerateVec(0, TOF))))
		le = 0, ri = TOF;
	else if (n > TOF)
		alwaysMarked = GenerateVec(0, TOF), le = TOF, ri = n, saved = 1;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		if (HasImpact(MarkAll(GenerateVec(0, md))))
			ri = md;
		else
			le = md;
	}
	alwaysMarked = GenerateVec(0, le);
	root = le;
	queue < int > qu;
	memset(H, -1, sizeof(H));
	H[root] = 0; qu.push(root);
	while (qu.size())
	{
		int v = qu.front();
		qu.pop();
		for (auto u : Adj[v])
			if (u.first >= le && H[u.first] == -1)
				H[u.first] = H[v] + 1, qu.push(u.first);
	}

	vector < int > Rs;
	vector < int > marked(n, 0);
	for (int i : alwaysMarked)
		marked[i] = 1;
	for (int w = 0; w < 2; w ++)
	{
      for (int i : alwaysMarked)
		marked[i] = 1;
		vector < int > srt;
		for (int i = 0; i < n; i ++)
			if (marked[i] == 0)
				srt.pb(i);
		sort(srt.begin(), srt.end(), [&](int i, int j){return H[i] > H[j];});

		auto GenVec = [&](int l, int r){
			assert(r <= (int)srt.size());
			vector < int > vec;
			for (int i = l; i < r; i ++)
				vec.pb(srt[i]);
			return vec;
		};

		le = 0, ri = (int)srt.size();
      	if (saved){}
		else if (srt.size() > TOF && HasImpact(MarkAll(GenVec(0, TOF))))
			le = 0, ri = TOF;
		else if (srt.size() > TOF)
		{
			for (int i = 0; i < TOF; i ++)
				alwaysMarked.pb(srt[i]);
			le = TOF;
          saved = 1;
		}

		while (ri - le > 1)
		{
			md = (le + ri) >> 1;
			if (HasImpact(MarkAll(GenVec(0, md))))
				ri = md;
			else
				le = md;
		}

		Rs.pb(srt[le]);
		qu.push(srt[le]);
		marked[srt[le]] = 1;
		while (qu.size())
		{
			int v = qu.front();
			qu.pop();
			for (auto u : Adj[v])
				if (!marked[u.first] && u.first != root && H[u.first] == H[v] - 1)
					marked[u.first] = 1, qu.push(u.first);
		}
	}
	assert((int)Rs.size() == 2);
	answer(Rs[0], Rs[1]);
	return ;

}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:93:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   93 |       for (int i : alwaysMarked)
      |       ^~~
highway.cpp:95:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |   vector < int > srt;
      |   ^~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 28 ms 3724 KB Output is correct
3 Correct 518 ms 10372 KB Output is correct
4 Correct 497 ms 10868 KB Output is correct
5 Correct 544 ms 10848 KB Output is correct
6 Correct 477 ms 10712 KB Output is correct
7 Correct 560 ms 10404 KB Output is correct
8 Correct 550 ms 10312 KB Output is correct
9 Correct 566 ms 10312 KB Output is correct
10 Correct 597 ms 10320 KB Output is correct
11 Correct 574 ms 9944 KB Output is correct
12 Correct 625 ms 9772 KB Output is correct
13 Correct 537 ms 9768 KB Output is correct
14 Correct 436 ms 10152 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3624 KB Output is correct
2 Correct 49 ms 4412 KB Output is correct
3 Correct 69 ms 5004 KB Output is correct
4 Correct 241 ms 9572 KB Output is correct
5 Correct 226 ms 9768 KB Output is correct
6 Correct 191 ms 9084 KB Output is correct
7 Correct 265 ms 9188 KB Output is correct
8 Correct 192 ms 9328 KB Output is correct
9 Correct 217 ms 9340 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 32 ms 3712 KB Output is correct
3 Correct 392 ms 8428 KB Output is correct
4 Correct 406 ms 9668 KB Output is correct
5 Correct 573 ms 10376 KB Output is correct
6 Correct 314 ms 10172 KB Output is correct
7 Correct 491 ms 10200 KB Output is correct
8 Correct 381 ms 9712 KB Output is correct
9 Correct 503 ms 10376 KB Output is correct
10 Correct 526 ms 10368 KB Output is correct
11 Correct 236 ms 9116 KB Output is correct
12 Correct 296 ms 8872 KB Output is correct
13 Correct 431 ms 9216 KB Output is correct
14 Correct 468 ms 9524 KB Output is correct
15 Correct 631 ms 10240 KB Output is correct
16 Correct 385 ms 9688 KB Output is correct
17 Correct 365 ms 9024 KB Output is correct
18 Correct 204 ms 9056 KB Output is correct
19 Correct 258 ms 9744 KB Output is correct
20 Correct 264 ms 8984 KB Output is correct
21 Correct 458 ms 10252 KB Output is correct
22 Correct 455 ms 10852 KB Output is correct
23 Correct 368 ms 9980 KB Output is correct
24 Correct 282 ms 9868 KB Output is correct
25 Correct 219 ms 9000 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3760 KB Output is correct
2 Correct 34 ms 3764 KB Output is correct
3 Correct 623 ms 11008 KB Output is correct
4 Correct 633 ms 11756 KB Output is correct
5 Correct 690 ms 12664 KB Output is correct
6 Correct 726 ms 12588 KB Output is correct
7 Correct 654 ms 12688 KB Output is correct
8 Correct 663 ms 12576 KB Output is correct
9 Correct 277 ms 10124 KB Output is correct
10 Correct 352 ms 10972 KB Output is correct
11 Correct 436 ms 10952 KB Output is correct
12 Correct 567 ms 12132 KB Output is correct
13 Correct 595 ms 12356 KB Output is correct
14 Correct 726 ms 12776 KB Output is correct
15 Correct 710 ms 12576 KB Output is correct
16 Correct 415 ms 11420 KB Output is correct
17 Correct 391 ms 10916 KB Output is correct
18 Correct 334 ms 11104 KB Output is correct
19 Correct 317 ms 11056 KB Output is correct
20 Correct 380 ms 10756 KB Output is correct
21 Correct 802 ms 12812 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3724 KB Output is correct
2 Correct 31 ms 3788 KB Output is correct
3 Correct 621 ms 11112 KB Output is correct
4 Correct 569 ms 11076 KB Output is correct
5 Correct 595 ms 11544 KB Output is correct
6 Correct 685 ms 12616 KB Output is correct
7 Correct 605 ms 10944 KB Output is correct
8 Correct 544 ms 11108 KB Output is correct
9 Correct 580 ms 11320 KB Output is correct
10 Correct 712 ms 12636 KB Output is correct
11 Correct 667 ms 12604 KB Output is correct
12 Correct 663 ms 12580 KB Output is correct
13 Correct 311 ms 10912 KB Output is correct
14 Correct 238 ms 10608 KB Output is correct
15 Correct 399 ms 10920 KB Output is correct
16 Correct 360 ms 10832 KB Output is correct
17 Correct 409 ms 10920 KB Output is correct
18 Correct 322 ms 10760 KB Output is correct
19 Correct 604 ms 12100 KB Output is correct
20 Correct 672 ms 12460 KB Output is correct
21 Correct 740 ms 12632 KB Output is correct
22 Correct 727 ms 12664 KB Output is correct
23 Correct 716 ms 12624 KB Output is correct
24 Correct 702 ms 12732 KB Output is correct
25 Correct 698 ms 12536 KB Output is correct
26 Correct 680 ms 12560 KB Output is correct
27 Correct 412 ms 10672 KB Output is correct
28 Correct 354 ms 10844 KB Output is correct
29 Correct 385 ms 11116 KB Output is correct
30 Correct 443 ms 11108 KB Output is correct
31 Correct 381 ms 10404 KB Output is correct
32 Correct 398 ms 10612 KB Output is correct
33 Correct 402 ms 10512 KB Output is correct
34 Correct 328 ms 11176 KB Output is correct
35 Correct 387 ms 10572 KB Output is correct
36 Correct 388 ms 10780 KB Output is correct
37 Correct 341 ms 10960 KB Output is correct
38 Correct 439 ms 10904 KB Output is correct
39 Correct 783 ms 12532 KB Output is correct
40 Correct 812 ms 12580 KB Output is correct
41 Correct 492 ms 12384 KB Output is correct
42 Correct 765 ms 12512 KB Output is correct