oj.uz

Submission #1072564

# Submission time Handle Problem Language Result Execution time Memory
1072564 2024-08-23T22:06:51 Z pawned Highway Tolls (IOI18_highway) C++17
51 / 100
 200 ms 19764 KB 
#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;
map<ii, int> conv;	// id of each edge

ll A, B;

ll lr, ds;

int findOther(int r) {	// find other endpoint from root
	queue<int> q;
	vi dist(N, 1e9);
	q.push(r);
	dist[r] = 0;
	vi goodid;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adj[x]) {
			if (dist[y] == 1e9) {
				dist[y] = dist[x] + 1;
				if (dist[y] == ds)
					goodid.pb(conv[{min(x, y), max(x, y)}]);
				q.push(y);
			}
		}
	}
/*	cout<<"goodid: ";
	for (int x : goodid)
		cout<<x<<" ";
	cout<<endl;*/
	int K = goodid.size();
//	cout<<"K: "<<K<<endl;
	int low = 0;
	int high = K - 1;
	int res = -1;	// first pos so traffic includes res
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
//		cout<<"at "<<mid<<endl;
		vi toask(M, 0);
		for (int i = 0; i <= mid; i++) {
			toask[goodid[i]] = true;
		}
		if (ask(toask) > lr) {
			res = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"res: "<<res<<endl;
	int sp = -1;	// second vertex
	if (dist[edges[goodid[res]].fi] == ds)
		sp = edges[goodid[res]].fi;
	else
		sp = edges[goodid[res]].se;
	return sp;
}

void find_pair(int N_g, vi U_g, vi V_g, int A_g, int B_g) {
	N = N_g;
	M = U_g.size();
	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);
	lr = ask(tq);
	ds = lr / A;
//	cout<<"lr, ds: "<<lr<<" "<<ds<<endl;
	// find all edges with distance ds-1 to ds
	queue<int> q;
	vi dist(N, 1e9);
	q.push(0);
	dist[0] = 0;
	int D = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		D = max(D, dist[x]);
		for (int y : adj[x]) {
			if (dist[y] == 1e9) {
				dist[y] = dist[x] + 1;
				q.push(y);
			}
		}
	}
	vi edgec[D + 1];
	// edgec[i] stores all id of edges w/ (deeper) depth i
	for (ii p : edges) {
		edgec[max(dist[p.fi], dist[p.se])].pb(conv[p]);
	}
	int low = 1;
	int high = D;
	int dr = -1;	// [dr-1, dr] is deepest w/ selected edge
	while (low <= high) {	// true, true, true, false, false, false
		// add all dr and above, see if has selected
		int mid = (low + high) / 2;
		vi tq(M, 0);
		for (int i = mid; i <= D; i++) {
			for (int x : edgec[i])
				tq[x] = 1;
		}
		if (ask(tq) > lr) {
			dr = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
//	cout<<"dr: "<<dr<<endl;
	low = 0;
	high = edgec[dr].size() - 1;
	int dt = -1;	// edgec[dr][dt] is the first selected
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi tq(M, 0);
		for (int i = 0; i <= mid; i++) {
			tq[edgec[dr][i]] = 1;
		}
		if (ask(tq) > lr) {
			dt = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"dt: "<<dt<<endl;
	int cid = edgec[dr][dt];
//	cout<<"cid: "<<cid<<endl;
	int s1 = -1;
	if (dist[edges[cid].fi] > dist[edges[cid].se])
		s1 = edges[cid].fi;
	else
		s1 = edges[cid].se;
//	cout<<"s1: "<<s1<<endl;
	int s2 = findOther(s1);
	answer(s1, s2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2904 KB Output is correct
2 Correct 14 ms 4216 KB Output is correct
3 Correct 130 ms 15452 KB Output is correct
4 Correct 150 ms 15672 KB Output is correct
5 Correct 124 ms 15500 KB Output is correct
6 Correct 145 ms 15436 KB Output is correct
7 Correct 135 ms 15456 KB Output is correct
8 Correct 128 ms 15488 KB Output is correct
9 Correct 134 ms 15516 KB Output is correct
10 Correct 132 ms 15276 KB Output is correct
11 Correct 137 ms 15960 KB Output is correct
12 Correct 145 ms 16684 KB Output is correct
13 Correct 143 ms 16128 KB Output is correct
14 Correct 139 ms 15792 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4696 KB Output is correct
2 Correct 19 ms 6356 KB Output is correct
3 Correct 27 ms 8292 KB Output is correct
4 Correct 89 ms 19604 KB Output is correct
5 Correct 92 ms 19512 KB Output is correct
6 Correct 103 ms 19592 KB Output is correct
7 Correct 82 ms 19628 KB Output is correct
8 Correct 88 ms 19608 KB Output is correct
9 Correct 98 ms 19580 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 12 ms 4136 KB Output is correct
3 Correct 88 ms 12416 KB Output is correct
4 Correct 127 ms 15320 KB Output is correct
5 Correct 125 ms 15396 KB Output is correct
6 Correct 120 ms 15348 KB Output is correct
7 Correct 114 ms 15380 KB Output is correct
8 Correct 138 ms 15244 KB Output is correct
9 Correct 132 ms 15452 KB Output is correct
10 Correct 137 ms 15928 KB Output is correct
11 Correct 136 ms 15844 KB Output is correct
12 Correct 143 ms 16428 KB Output is correct
13 Correct 147 ms 16136 KB Output is correct
14 Correct 152 ms 16448 KB Output is correct
15 Correct 131 ms 15160 KB Output is correct
16 Correct 126 ms 15236 KB Output is correct
17 Correct 137 ms 16328 KB Output is correct
18 Correct 151 ms 16140 KB Output is correct
19 Correct 122 ms 15176 KB Output is correct
20 Correct 130 ms 16888 KB Output is correct
21 Correct 132 ms 16404 KB Output is correct
22 Correct 139 ms 16460 KB Output is correct
23 Correct 149 ms 16108 KB Output is correct
24 Correct 153 ms 16584 KB Output is correct
25 Correct 158 ms 19032 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4184 KB Output is correct
2 Correct 15 ms 4384 KB Output is correct
3 Correct 166 ms 16432 KB Output is correct
4 Correct 166 ms 17600 KB Output is correct
5 Incorrect 200 ms 19764 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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