oj.uz

Submission #999342

# Submission time Handle Problem Language Result Execution time Memory
999342 2024-06-15T10:25:14 Z Unforgettablepl Highway Tolls (IOI18_highway) C++17
51 / 100
 221 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()

long long ask(const std::vector<int> &w);
void answer(int s, int t);

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	vector<vector<pair<int,int>>> adj(N);
	for(int i=0;i<U.size();i++){
		adj[U[i]].emplace_back(V[i],i);
		adj[V[i]].emplace_back(U[i],i);
	}
	vector<int> pedge(N);
	vector<int> depth(N);
	function<void(int,int,int,int)> dfs = [&](int x,int p,int dep,int par){
		depth[x]=dep;
		pedge[x]=par;
		for(auto&i:adj[x])if(i.first!=p)dfs(i.first,x,dep+1,i.second);
	};
	dfs(0,-1,0,-1);
	int M = U.size();
	auto base = ask(vector<int>(M));
	auto basedep = base/((long long)A);
	// Calculate st
	vector<pair<int,int>> arr;
	for(int i=0;i<N;i++)arr.emplace_back(depth[i],i);
	sort(arr.rbegin(),arr.rend());
	auto check = [&](int x){
		vector<int> wt(M);
		for(int i=0;i<x;i++)wt[pedge[arr[i].second]]=1;
		return base==ask(wt);
	};
	int st = 0;
	for(int jump = 65536;jump;jump/=2){
		if(st+jump>=N)continue;
		if(check(st+jump))st+=jump;
	}
	st = arr[st].second;
	dfs(st,-1,0,-1);
	vector<int> sus;
	for(int i=0;i<N;i++)if(depth[i]==basedep)sus.emplace_back(i);
	while(sus.size()>1){
		int mid = (sus.size())/2;
		vector<int> left,right;
		for(int i=0;i<mid;i++)left.emplace_back(sus[i]);
		for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
		vector<int> w(M);
		for(int&i:left)w[pedge[i]]=1;
		auto ans = ask(w);
		if(ans!=base)sus=left;
		else sus=right;
	}
	answer(st, sus[0]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<U.size();i++){
      |              ~^~~~~~~~~
highway.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1276 KB Output is correct
3 Correct 99 ms 9744 KB Output is correct
4 Correct 91 ms 9476 KB Output is correct
5 Correct 97 ms 9800 KB Output is correct
6 Correct 89 ms 9476 KB Output is correct
7 Correct 103 ms 9480 KB Output is correct
8 Correct 93 ms 9476 KB Output is correct
9 Correct 82 ms 9492 KB Output is correct
10 Correct 89 ms 9472 KB Output is correct
11 Correct 89 ms 10992 KB Output is correct
12 Correct 94 ms 11868 KB Output is correct
13 Correct 97 ms 11024 KB Output is correct
14 Correct 88 ms 10988 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2208 KB Output is correct
2 Correct 15 ms 4184 KB Output is correct
3 Correct 22 ms 6212 KB Output is correct
4 Correct 70 ms 17308 KB Output is correct
5 Correct 68 ms 17388 KB Output is correct
6 Correct 70 ms 17404 KB Output is correct
7 Correct 69 ms 17420 KB Output is correct
8 Correct 73 ms 17392 KB Output is correct
9 Correct 63 ms 17648 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1280 KB Output is correct
3 Correct 71 ms 7356 KB Output is correct
4 Correct 90 ms 9456 KB Output is correct
5 Correct 78 ms 9456 KB Output is correct
6 Correct 86 ms 9456 KB Output is correct
7 Correct 83 ms 9456 KB Output is correct
8 Correct 81 ms 9456 KB Output is correct
9 Correct 101 ms 9456 KB Output is correct
10 Correct 85 ms 9456 KB Output is correct
11 Correct 89 ms 10540 KB Output is correct
12 Correct 91 ms 12028 KB Output is correct
13 Correct 89 ms 11268 KB Output is correct
14 Correct 89 ms 11796 KB Output is correct
15 Correct 83 ms 9456 KB Output is correct
16 Correct 78 ms 9456 KB Output is correct
17 Correct 94 ms 11540 KB Output is correct
18 Correct 107 ms 11464 KB Output is correct
19 Correct 85 ms 9472 KB Output is correct
20 Correct 85 ms 12556 KB Output is correct
21 Correct 94 ms 10492 KB Output is correct
22 Correct 75 ms 10528 KB Output is correct
23 Correct 81 ms 9780 KB Output is correct
24 Correct 80 ms 10748 KB Output is correct
25 Correct 92 ms 16120 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 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 200 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -