oj.uz

Submission #1072529

# Submission time Handle Problem Language Result Execution time Memory
1072529 2024-08-23T21:19:55 Z pawned Highway Tolls (IOI18_highway) C++17
12 / 100
 106 ms 14648 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;

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;
//	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;
	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;
		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;
//	cout<<"sp: "<<sp<<endl;
	answer(0, sp);
}

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 2656 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 2636 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 12 ms 4024 KB Output is correct
3 Correct 106 ms 14616 KB Output is correct
4 Correct 98 ms 14616 KB Output is correct
5 Correct 97 ms 14532 KB Output is correct
6 Correct 106 ms 14576 KB Output is correct
7 Correct 96 ms 14560 KB Output is correct
8 Correct 95 ms 14532 KB Output is correct
9 Correct 103 ms 14340 KB Output is correct
10 Correct 103 ms 14648 KB Output is correct
11 Correct 92 ms 14360 KB Output is correct
12 Correct 97 ms 14276 KB Output is correct
13 Correct 105 ms 14276 KB Output is correct
14 Correct 103 ms 14276 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4184 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 11 ms 4184 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -