oj.uz

Submission #978898

# Submission time Handle Problem Language Result Execution time Memory
978898 2024-05-10T01:09:35 Z happypotato Highway Tolls (IOI18_highway) C++17
51 / 100
 223 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 1e5;
vector<pii> adj[mxN];
int par[mxN];
int paredge[mxN];
int depth[mxN];
void dfs1(int u = 0, int dep = 0, int pp = -1) {
	depth[u] = dep;
	for (pii v : adj[u]) {
		if (v.ff == pp) continue;
		paredge[v.ff] = v.ss;
		par[v.ff] = u;
		dfs1(v.ff, dep + 1, u);
	}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size();
	vector<pair<pii, int>> edges(m);
	for (int i = 0; i < m; i++) {
		edges[i] = {{U[i], V[i]}, i};
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	vector<int> pass(m, 0);
	ll base = ask(pass);
	dfs1(); paredge[0] = -1;
	int S, T, LCA, ldep;
	// search for last element
	{
		vector<pii> v;
		for (int i = 1; i < n; i++) {
			v.pb({depth[i], i});
		}
		sort(v.begin(), v.end(), greater<pii>());
		int lb = 0, rb = (int)(v.size()) - 1;
		while (lb < rb) {
			int mid = (lb + rb + 1) >> 1;
			for (int i = 0; i < mid; i++) pass[paredge[v[i].ss]] = 1;
			ll ret = ask(pass);
			if (ret == base) lb = mid;
			else rb = mid - 1;
			for (int i = 0; i < mid; i++) pass[paredge[v[i].ss]] = 0;
		}
		S = v[lb].ss;
	}
	// search for depth of LCA
	{
		int lb = 0, rb = n;
		while (lb < rb) {
			int mid = (lb + rb + 1) >> 1;
			for (int i = 1; i < n; i++) {
				pass[paredge[i]] = (depth[i] <= mid);
			}
			ll ret = ask(pass);
			if (ret == base) lb = mid;
			else rb = mid - 1;
			for (int i = 0; i < m; i++) pass[i] = 0;
		}
		ldep = lb;
	}
	LCA = S;
	for (int i = depth[S]; i > ldep; i--) LCA = par[LCA];
	if (1LL * (depth[S] - ldep) * A == base) return answer(LCA, S);
	int rdep = (base / A) - (depth[S] - ldep) + ldep;
	int avoid = S;
	for (int i = depth[S]; i > rdep; i--) avoid = par[avoid];
	// search for remaining node
	{
		vector<int> v;
		for (int i = 0; i < n; i++) {
			if (depth[i] == rdep && i != avoid) v.pb(i);
		}
		int lb = 0, rb = (int)(v.size()) - 1;
		while (lb < rb) {
			int mid = (lb + rb) >> 1;
			for (int i = 0; i <= mid; i++) pass[paredge[v[i]]] = 1;
			ll ret = ask(pass);
			if (ret != base) rb = mid;
			else lb = mid + 1;
			for (int i = 0; i <= mid; i++) pass[paredge[v[i]]] = 0;
		}
		T = v[lb];
	}
	answer(S, T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3856 KB Output is correct
2 Correct 11 ms 4876 KB Output is correct
3 Correct 89 ms 11200 KB Output is correct
4 Correct 101 ms 11424 KB Output is correct
5 Correct 98 ms 11128 KB Output is correct
6 Correct 92 ms 11232 KB Output is correct
7 Correct 98 ms 11212 KB Output is correct
8 Correct 78 ms 11108 KB Output is correct
9 Correct 97 ms 11284 KB Output is correct
10 Correct 92 ms 11348 KB Output is correct
11 Correct 99 ms 12108 KB Output is correct
12 Correct 98 ms 12620 KB Output is correct
13 Correct 95 ms 12140 KB Output is correct
14 Correct 100 ms 11596 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5188 KB Output is correct
2 Correct 18 ms 6912 KB Output is correct
3 Correct 26 ms 7984 KB Output is correct
4 Correct 105 ms 16192 KB Output is correct
5 Correct 73 ms 16488 KB Output is correct
6 Correct 73 ms 16192 KB Output is correct
7 Correct 100 ms 16304 KB Output is correct
8 Correct 107 ms 16200 KB Output is correct
9 Correct 75 ms 16368 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3852 KB Output is correct
2 Correct 14 ms 4724 KB Output is correct
3 Correct 82 ms 9924 KB Output is correct
4 Correct 123 ms 11128 KB Output is correct
5 Correct 92 ms 11256 KB Output is correct
6 Correct 110 ms 11112 KB Output is correct
7 Correct 85 ms 11244 KB Output is correct
8 Correct 129 ms 11668 KB Output is correct
9 Correct 93 ms 11220 KB Output is correct
10 Correct 96 ms 11120 KB Output is correct
11 Correct 101 ms 11500 KB Output is correct
12 Correct 100 ms 12692 KB Output is correct
13 Correct 118 ms 12236 KB Output is correct
14 Correct 111 ms 12608 KB Output is correct
15 Correct 113 ms 11220 KB Output is correct
16 Correct 84 ms 11116 KB Output is correct
17 Correct 118 ms 12372 KB Output is correct
18 Correct 94 ms 12000 KB Output is correct
19 Correct 116 ms 11220 KB Output is correct
20 Correct 92 ms 13136 KB Output is correct
21 Correct 115 ms 11680 KB Output is correct
22 Correct 104 ms 11680 KB Output is correct
23 Correct 142 ms 11524 KB Output is correct
24 Correct 129 ms 11976 KB Output is correct
25 Correct 109 ms 15516 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -