oj.uz

Submission #807628

# Submission time Handle Problem Language Result Execution time Memory
807628 2023-08-04T20:42:48 Z Lobo Highway Tolls (IOI18_highway) C++17
51 / 100
 183 ms 17976 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
const int inf = 1e18+10;
const int maxn = 9e4+10;

int n, m, par[maxn];
vector<int> parid[maxn];
vector<int> g[maxn];

void find_pair(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A, int32_t B) {
	// int M = U.size();
	// for (int j = 0; j < 50; ++j) {
	//   std::vector<int> w(M);
	//   for (int i = 0; i < M; ++i) {
	//     w[i] = 0;
	//   }
	//   long long toll = ask(w);
	// }
	// answer(0, N - 1);


	n = N;
	m = U.size();
	for(int i = 0; i < m; i++) {
		g[U[i]].pb(i);
		g[V[i]].pb(i);
	}
	vector<int32_t> vectudoa(m,0);
	int tudoa = ask(vectudoa);
	int path = tudoa/A;

	int edgein = -1;
	int lbs,rbs;
	vector<int32_t> vectoll(m,0);
	lbs = 0;
	rbs = m-1;
	while(lbs <= rbs) {
		int mid = (lbs+rbs)/2;
		vectoll.clear(); vectoll.resize(m,0);
		for(int i = 0; i <= mid; i++) {
			vectoll[i] = 1;
		}

		int toll = ask(vectoll);

		if(toll != tudoa) {
			edgein = mid;
			rbs = mid-1;
		}
		else {
			lbs = mid+1;
		}
	}

	assert(edgein != -1);

	int ss = U[edgein];
	int tt = V[edgein];

	vector<pair<int,int>> d(n+10,mp(inf,0));
	d[ss] = mp(0,ss); par[ss] = -1;
	d[tt] = mp(0,tt); par[tt] = -1;

	queue<int> q; q.push(ss); q.push(tt);
	while(q.size()) {
		int u = q.front(); q.pop();

		for(auto id : g[u]) {
			int v = U[id]+V[id]-u;
			if(d[v].fr > d[u].fr+1) {
				d[v] = mp(d[u].fr+1,d[u].sc);
				par[v] = u;
				parid[v].clear(); parid[v].pb(id);
				q.push(v);
			}
			else if(d[v].fr == d[u].fr+1) {
				parid[v].pb(id);
			}
		}
	}

	int toll0;

	vector<pair<int,int>> Ds;
	for(int i = 0; i < n; i++) {
		if(d[i].sc == ss) {
			Ds.pb(mp(d[i].fr,i));
		}
	}
	sort(all(Ds));
	lbs = 0;
	rbs = (int) Ds.size()-1;
	int32_t s = -1;

	vectoll.clear(); vectoll.resize(m,1);
	for(int i = 0; i < (int) Ds.size(); i++) {
		for(auto id : parid[Ds[i].sc]) vectoll[id] = 0;
		// if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
	}
	toll0 = ask(vectoll);

	while(lbs <= rbs) {
		int mid = (lbs+rbs)/2;

		vectoll.clear(); vectoll.resize(m,1);

		// for(int i = 0; i <= mid; i++) {
		// 	if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 0;
		// }

		for(int i = 0; i <= mid; i++) {
			for(auto id : parid[Ds[i].sc]) vectoll[id] = 0;
			// if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
		}

		int toll = ask(vectoll);

		if(toll == toll0) {
			s = Ds[mid].sc;
			rbs = mid-1;
		}
		else {
			lbs = mid+1;
		}
	}

	vector<pair<int,int>> Dt;
	for(int i = 0; i < n; i++) {
		if(d[i].sc == tt) {
			Dt.pb(mp(d[i].fr,i));
		}
	}
	sort(all(Dt));
	lbs = 0;
	rbs = (int) Dt.size()-1;
	int32_t t = -1;

	vectoll.clear(); vectoll.resize(m,1);
	for(int i = 0; i < (int) Dt.size(); i++) {
		for(auto id : parid[Dt[i].sc]) vectoll[id] = 0;
		// if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
	}
	toll0 = ask(vectoll);

	while(lbs <= rbs) {
		int mid = (lbs+rbs)/2;

		vectoll.clear(); vectoll.resize(m,1);

		// for(int i = 0; i <= mid; i++) {
		// 	if(parid[Dt[i].sc] != -1) vectoll[parid[Dt[i].sc]] = 0;
		// }

		for(int i = 0; i <= mid; i++) {
			for(auto id : parid[Dt[i].sc]) vectoll[id] = 0;
			// if(parid[Dt[i].sc] != -1) vectoll[parid[Dt[i].sc]] = 1;
		}

		int toll = ask(vectoll);

		if(toll == toll0) {
			t = Dt[mid].sc;
			rbs = mid-1;
		}
		else {
			lbs = mid+1;
		}
	}

	// cout << ss << " " << tt << endl;
	// cout << s << " " << t << endl;
	answer(s,t);
}

Compilation message

highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:37:6: warning: unused variable 'path' [-Wunused-variable]
   37 |  int path = tudoa/A;
      |      ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4540 KB Output is correct
2 Correct 2 ms 4452 KB Output is correct
3 Correct 2 ms 4540 KB Output is correct
4 Correct 2 ms 4544 KB Output is correct
5 Correct 2 ms 4472 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 2 ms 4432 KB Output is correct
8 Correct 2 ms 4548 KB Output is correct
9 Correct 2 ms 4544 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 3 ms 4432 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4560 KB Output is correct
2 Correct 12 ms 6000 KB Output is correct
3 Correct 155 ms 17072 KB Output is correct
4 Correct 142 ms 17152 KB Output is correct
5 Correct 129 ms 17064 KB Output is correct
6 Correct 132 ms 17072 KB Output is correct
7 Correct 120 ms 17096 KB Output is correct
8 Correct 121 ms 17160 KB Output is correct
9 Correct 138 ms 17112 KB Output is correct
10 Correct 144 ms 17064 KB Output is correct
11 Correct 150 ms 16664 KB Output is correct
12 Correct 124 ms 16476 KB Output is correct
13 Correct 118 ms 16600 KB Output is correct
14 Correct 123 ms 16496 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5968 KB Output is correct
2 Correct 20 ms 7240 KB Output is correct
3 Correct 25 ms 8412 KB Output is correct
4 Correct 77 ms 16468 KB Output is correct
5 Correct 93 ms 16348 KB Output is correct
6 Correct 76 ms 16832 KB Output is correct
7 Correct 72 ms 16544 KB Output is correct
8 Correct 110 ms 15932 KB Output is correct
9 Correct 96 ms 16564 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4560 KB Output is correct
2 Correct 14 ms 5920 KB Output is correct
3 Correct 75 ms 14844 KB Output is correct
4 Correct 138 ms 17088 KB Output is correct
5 Correct 127 ms 17120 KB Output is correct
6 Correct 97 ms 17140 KB Output is correct
7 Correct 137 ms 17204 KB Output is correct
8 Correct 130 ms 17040 KB Output is correct
9 Correct 183 ms 17044 KB Output is correct
10 Correct 123 ms 17044 KB Output is correct
11 Correct 110 ms 16536 KB Output is correct
12 Correct 121 ms 16720 KB Output is correct
13 Correct 130 ms 16532 KB Output is correct
14 Correct 135 ms 16336 KB Output is correct
15 Correct 140 ms 17044 KB Output is correct
16 Correct 140 ms 17140 KB Output is correct
17 Correct 133 ms 16472 KB Output is correct
18 Correct 119 ms 16528 KB Output is correct
19 Correct 116 ms 17028 KB Output is correct
20 Correct 103 ms 16640 KB Output is correct
21 Correct 148 ms 17976 KB Output is correct
22 Correct 118 ms 17920 KB Output is correct
23 Correct 115 ms 17628 KB Output is correct
24 Correct 133 ms 17568 KB Output is correct
25 Correct 150 ms 16692 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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