oj.uz

Submission #1017470

# Submission time Handle Problem Language Result Execution time Memory
1017470 2024-07-09T08:15:23 Z mansur Highway Tolls (IOI18_highway) C++17
51 / 100
 126 ms 37128 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e6;

vector<pii> g[N];

int n, m1;

void find_pair(int n1, vector<int> u, vector<int> v, int a, int b) {
	n = n1, m1 = sz(u);
	for (int i = 0; i < m1; i++) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}
	vector<int> w(sz(u));
	ll dt = ask(w);	
	int l = 0, r = sz(u) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[i] = 1;
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[i] = 0;
	}
	int x = u[l], y = v[l];
	queue<int> q;
	vector<int> d(n, -1), tp(n, -1), is(m1);
	vector<pii> s[2][n];
	d[x] = 0, d[y] = 0;
	tp[x] = 0, tp[y] = 1;
	is[l] = -1;
	s[0][0] = {{x, l}};
	s[1][0] = {{y, l}};
	q.push(x);
	q.push(y);
	while (sz(q)) {
		int a = q.front();
		q.pop();
		for (auto [to, id]: g[a]) {
			if (d[to] == -1) {
				tp[to] = tp[a];
            	d[to] = d[a] + 1;
            	q.push(to);
				s[tp[to]][d[to]].push_back({to, id});
            	is[id] = 1;
            }
		}
	}
	for (int i = 0; i < m1; i++) {
		if (!is[i]) {
			w[i] = 1;
			continue;
		}
	}
	for (int i = 0; i < m1; i++) {
		if (is[i] == 1 && tp[u[i]]) w[i] = 1;		
	}
	ll td = ask(w);
	int dt1 = (td - dt) / (b - a);
	for (int i = 0; i < m1; i++) {
		if (is[i] == 1 && tp[u[i]]) w[i] = 0;		
	}
	int dt0 = dt / a - dt1 - 1;
	l = 0, r = sz(s[0][dt0]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			w[s[0][dt0][i].s] = 1;
	 	}
	 	if (ask(w) == dt) l = m + 1;
	 	else r = m - 1;
	 	for (int i = 0; i <= m; i++) {
			w[s[0][dt0][i].s] = 0;
	 	}
	}
	int ans0 = s[0][dt0][l].f;
	l = 0, r = sz(s[1][dt1]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			w[s[1][dt1][i].s] = 1;
	 	}
	 	if (ask(w) == dt) l = m + 1;
	 	else r = m - 1;
	 	for (int i = 0; i <= m; i++) {
			w[s[1][dt1][i].s] = 0;
	 	}
	}
	int ans1 = s[1][dt1][l].f;
	answer(ans0, ans1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23896 KB Output is correct
2 Correct 11 ms 23896 KB Output is correct
3 Correct 13 ms 23848 KB Output is correct
4 Correct 11 ms 23928 KB Output is correct
5 Correct 9 ms 23728 KB Output is correct
6 Correct 10 ms 23896 KB Output is correct
7 Correct 10 ms 23896 KB Output is correct
8 Correct 10 ms 23896 KB Output is correct
9 Correct 9 ms 23896 KB Output is correct
10 Correct 10 ms 23896 KB Output is correct
11 Correct 12 ms 23760 KB Output is correct
12 Correct 12 ms 23896 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 16 ms 25036 KB Output is correct
3 Correct 86 ms 35180 KB Output is correct
4 Correct 99 ms 35164 KB Output is correct
5 Correct 82 ms 35140 KB Output is correct
6 Correct 90 ms 35136 KB Output is correct
7 Correct 105 ms 35188 KB Output is correct
8 Correct 85 ms 35144 KB Output is correct
9 Correct 88 ms 35196 KB Output is correct
10 Correct 92 ms 35164 KB Output is correct
11 Correct 98 ms 35140 KB Output is correct
12 Correct 87 ms 35104 KB Output is correct
13 Correct 90 ms 34892 KB Output is correct
14 Correct 86 ms 35140 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25176 KB Output is correct
2 Correct 23 ms 26644 KB Output is correct
3 Correct 31 ms 27952 KB Output is correct
4 Correct 75 ms 36520 KB Output is correct
5 Correct 74 ms 36588 KB Output is correct
6 Correct 79 ms 36432 KB Output is correct
7 Correct 75 ms 36364 KB Output is correct
8 Correct 72 ms 36612 KB Output is correct
9 Correct 69 ms 36504 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 19 ms 25208 KB Output is correct
3 Correct 70 ms 32644 KB Output is correct
4 Correct 91 ms 35140 KB Output is correct
5 Correct 87 ms 35208 KB Output is correct
6 Correct 87 ms 35088 KB Output is correct
7 Correct 77 ms 35104 KB Output is correct
8 Correct 97 ms 35140 KB Output is correct
9 Correct 92 ms 35184 KB Output is correct
10 Correct 93 ms 35168 KB Output is correct
11 Correct 90 ms 34832 KB Output is correct
12 Correct 87 ms 35152 KB Output is correct
13 Correct 105 ms 35140 KB Output is correct
14 Correct 88 ms 35096 KB Output is correct
15 Correct 101 ms 35132 KB Output is correct
16 Correct 82 ms 34984 KB Output is correct
17 Correct 87 ms 35108 KB Output is correct
18 Correct 94 ms 35140 KB Output is correct
19 Correct 80 ms 35164 KB Output is correct
20 Correct 89 ms 35108 KB Output is correct
21 Correct 81 ms 36176 KB Output is correct
22 Correct 82 ms 36216 KB Output is correct
23 Correct 92 ms 35756 KB Output is correct
24 Correct 96 ms 35892 KB Output is correct
25 Correct 106 ms 36652 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 25176 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 Correct 18 ms 25176 KB Output is correct
2 Correct 19 ms 25084 KB Output is correct
3 Correct 97 ms 35636 KB Output is correct
4 Correct 105 ms 35984 KB Output is correct
5 Correct 108 ms 36152 KB Output is correct
6 Correct 126 ms 37128 KB Output is correct
7 Correct 98 ms 35656 KB Output is correct
8 Incorrect 103 ms 35948 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -