Submission #1072538

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1072538	2024-08-23T21:28:23 Z	pawned	Highway Tolls (IOI18_highway)	C++17	6 / 100	84 ms	14064 KB

highway

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "highway.h"

const int MAX = 1e5 + 5;

int N, M;

vi adj[MAX];

vector<ii> edges;

ll A, B;

void find_pair(int N_g, vi U_g, vi V_g, int A_g, int B_g) {
	N = N_g;
	int M = U_g.size();
	map<ii, int> conv;	// id of each edge
	for (int i = 0; i < M; i++) {
		adj[U_g[i]].pb(V_g[i]);
		adj[V_g[i]].pb(U_g[i]);
		edges.pb({min(U_g[i], V_g[i]), max(U_g[i], V_g[i])});
		conv[edges.back()] = i;
	}
	A = A_g; B = B_g;
	vi tq(M, 0);
	ll lr = ask(tq);
	ll ds = lr / A;
	int low = 0;
	int high = M - 1;
	int res = -1;	// first edge that's part
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi tq(M, 0);
		for (int j = 0; j <= mid; j++) {
			tq[j] = 1;
		}
		if (ask(tq) > lr) {
			res = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	answer(res, res + ds);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3928 KB	Output is correct
2	Correct	12 ms	5076 KB	Output is correct
3	Correct	27 ms	6472 KB	Output is correct
4	Correct	70 ms	14056 KB	Output is correct
5	Correct	73 ms	14056 KB	Output is correct
6	Correct	72 ms	14024 KB	Output is correct
7	Correct	68 ms	14064 KB	Output is correct
8	Correct	73 ms	14020 KB	Output is correct
9	Correct	84 ms	14064 KB	Output is correct