oj.uz

Submission #1063447

# Submission time Handle Problem Language Result Execution time Memory
1063447 2024-08-17T18:37:58 Z Tob Highway Tolls (IOI18_highway) C++14
51 / 100
 185 ms 14740 KB 
#include <bits/stdc++.h>

#include "highway.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int maxN = 90007;

ll odis;
int bio[maxN], dub[maxN];
vector <pii> adj[maxN];

void dfs(int x) {
	bio[x] = 1;
	for (auto y : adj[x]) {
		if (bio[y.F]) continue;
		dub[y.F] = dub[x]+1;
		dfs(y.F);
	}
}

void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
	int m = u.size();
	vector <int> tmp(m, 0);
	odis = ask(tmp);
	for (int i = 0; i < m; i++) {
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	dfs(0);
	
	vector <int> e;
	for (int i = 0; i < m; i++) e.pb(i);
	
	sort(all(e), [&](int x, int y) {return max(dub[u[x]], dub[v[x]]) > max(dub[u[y]], dub[v[y]]);});
	int lo = 0, hi = m-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		vector <int> ed(m, 0);
		for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
		if (odis != ask(ed)) hi = mid;
		else lo = mid+1;
	}
	int nx = u[e[lo]], ny = v[e[lo]];
	
	auto bfs = [&](vector <int> vv) {
		queue <int> q;
		memset(bio, -1, sizeof bio);
		for (auto x : vv) {
			bio[x] = 0;
			q.push(x);
		}
		vector <int> tmp(m, 1);
		while (!q.empty()) {
			int x = q.front(); q.pop();
			for (auto y : adj[x]) {
				if (bio[y.F] != -1) continue;
				bio[y.F] = bio[x] + 1;
				tmp[y.S] = 0;
				q.push(y.F);
			}
		}
		
		vector <int> e;
		for (int i = 0; i < m; i++) e.pb(i);
		sort(all(e), [&](int x, int y){return max(bio[v[x]], bio[u[x]]) < max(bio[v[y]], bio[u[y]]);});
		lo = 0, hi = m-1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			vector <int> ed; ed = tmp;
			for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
			if (odis/a*b != ask(ed)) lo = mid+1;
			else hi = mid;
		}
		int xx = u[e[lo]];
		if (bio[v[e[lo]]] > bio[xx]) xx = v[e[lo]];
		return xx;
	};
	
	int z = bfs({nx, ny});
	int w = bfs({z});
	
	answer(z, w);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2732 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 2 ms 2808 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 2 ms 2752 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 2 ms 2904 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 1 ms 2904 KB Output is correct
12 Correct 1 ms 2904 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 11 ms 3672 KB Output is correct
3 Correct 124 ms 9984 KB Output is correct
4 Correct 130 ms 9984 KB Output is correct
5 Correct 124 ms 10212 KB Output is correct
6 Correct 110 ms 9992 KB Output is correct
7 Correct 125 ms 10700 KB Output is correct
8 Correct 110 ms 9988 KB Output is correct
9 Correct 107 ms 9996 KB Output is correct
10 Correct 114 ms 9984 KB Output is correct
11 Correct 130 ms 10428 KB Output is correct
12 Correct 150 ms 11040 KB Output is correct
13 Correct 139 ms 10528 KB Output is correct
14 Correct 135 ms 10432 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3928 KB Output is correct
2 Correct 19 ms 5136 KB Output is correct
3 Correct 31 ms 6356 KB Output is correct
4 Correct 91 ms 13860 KB Output is correct
5 Correct 91 ms 13624 KB Output is correct
6 Correct 87 ms 13660 KB Output is correct
7 Correct 71 ms 13528 KB Output is correct
8 Correct 90 ms 13640 KB Output is correct
9 Correct 87 ms 13572 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 10 ms 3672 KB Output is correct
3 Correct 80 ms 8436 KB Output is correct
4 Correct 118 ms 9980 KB Output is correct
5 Correct 101 ms 9976 KB Output is correct
6 Correct 107 ms 10204 KB Output is correct
7 Correct 111 ms 9928 KB Output is correct
8 Correct 110 ms 9868 KB Output is correct
9 Correct 128 ms 10088 KB Output is correct
10 Correct 133 ms 9988 KB Output is correct
11 Correct 167 ms 10024 KB Output is correct
12 Correct 154 ms 10936 KB Output is correct
13 Correct 145 ms 10588 KB Output is correct
14 Correct 164 ms 11136 KB Output is correct
15 Correct 116 ms 9984 KB Output is correct
16 Correct 125 ms 10196 KB Output is correct
17 Correct 151 ms 10912 KB Output is correct
18 Correct 158 ms 10612 KB Output is correct
19 Correct 124 ms 9952 KB Output is correct
20 Correct 141 ms 11264 KB Output is correct
21 Correct 103 ms 10836 KB Output is correct
22 Correct 101 ms 10584 KB Output is correct
23 Correct 100 ms 10212 KB Output is correct
24 Correct 111 ms 10612 KB Output is correct
25 Correct 148 ms 13220 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3824 KB Output is correct
2 Incorrect 15 ms 3932 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4088 KB Output is correct
2 Correct 14 ms 3924 KB Output is correct
3 Partially correct 139 ms 11424 KB Output is partially correct
4 Partially correct 154 ms 12288 KB Output is partially correct
5 Partially correct 164 ms 12524 KB Output is partially correct
6 Partially correct 185 ms 14540 KB Output is partially correct
7 Partially correct 141 ms 11464 KB Output is partially correct
8 Correct 157 ms 11836 KB Output is correct
9 Partially correct 158 ms 12340 KB Output is partially correct
10 Incorrect 182 ms 14740 KB Output is incorrect: {s, t} is wrong.
11 Halted 0 ms 0 KB -