Submission #725667

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
725667	2023-04-17T20:35:07 Z	FatihSolak	Highway Tolls (IOI18_highway)	C++17	100 / 100	230 ms	14516 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<pair<int,int>> adj[N];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	int m = u.size();
	vector<int> w(m,0);
	long long len = ask(w) / a;
	int l = 0,r = m-1;
	while(l < r){
		int m = (l + r)/2;
		for(int i = l;i<=m;i++){
			w[i] = 1;
		}
		if(ask(w) != len * a){
			for(int i = l;i<=m;i++){
				w[i] = 0;
			}
			r = m;
		}
		else l = m + 1;
	}
	for(int i = 0;i<m;i++){
		adj[u[i]].push_back({v[i],i});
		adj[v[i]].push_back({u[i],i});
	}
	// cout << "LEN:";
	// cout << len << endl;
	// cout << "EDGE:";
	// cout << u[l] << ' ' << v[l] << endl;
	queue<int> q;
	auto bfs = [&](int v){
		vector<int> d(n,-1);
		vector<int> par(n,-1);
		queue<int> q;
		q.push(v);
		d[v] = 0;
		while(q.size()){
			auto tp = q.front();
			q.pop();
			for(auto u:adj[tp]){
				if(d[u.first] == -1){
					d[u.first] = d[tp] + 1;
					par[u.first] = u.second;
					q.push(u.first);
				}
			}
		}
		return make_pair(d,par);
	};
	auto x1 = bfs(u[l]);
	auto x2 = bfs(v[l]);
	vector<int> ord1;
	vector<int> ord2;
	w.assign(m,1);
	for(int i = 0;i<n;i++){
		if(x1.first[i] < x2.first[i]){
			ord1.push_back(i);
			if(x1.second[i] != -1)
				w[x1.second[i]] = 0;
		}
		else if(x2.first[i] < x1.first[i]){
			ord2.push_back(i);
			if(x2.second[i] != -1)
				w[x2.second[i]] = 0;
		}
	}
	w[l] = 0;
	sort(ord1.begin(),ord1.end(),[&](int a,int b){
		return x1.first[a] < x1.first[b];
	});
	sort(ord2.begin(),ord2.end(),[&](int a,int b){
		return x2.first[a] < x2.first[b];
	});
	// for(int i = 0;i<m;i++){
	// 	if(w[i] == 0){
	// 		cout << "EDGES:";
	// 		cout << u[i] << ' ' << v[i] << endl;
	// 	}
	// }
	// cout << "FIRST COMP";
	// for(auto u:ord1){
	// 	cout << u << ' ';
	// }
	// cout << endl;
	// cout << "SECOND COMP";
	// for(auto u:ord2){
	// 	cout << u << ' ';
	// }
	// cout << endl;
	int s = -1;
	int t = -1;
	l = 0, r = (int)ord1.size() - 1;
	while(l < r){
		int m = (l + r)/2;
		for(int i = m+1;i<=r;i++){
			w[x1.second[ord1[i]]] = 1;
		}
		if(ask(w) == len * a){
			r = m;
		}
		else{
			for(int i = m+1;i<=r;i++){
				w[x1.second[ord1[i]]] = 0;
			}
			l = m+1;
		}
	}
	s = ord1[l];
	l = 0, r = (int)ord2.size() - 1;
	while(l < r){
		int m = (l + r)/2;
		for(int i = m+1;i<=r;i++){
			w[x2.second[ord2[i]]] = 1;
		}
		if(ask(w) == len * a){
			r = m;
		}
		else{
			for(int i = m+1;i<=r;i++){
				w[x2.second[ord2[i]]] = 0;
			}
			l = m+1;
		}
	}
	t = ord2[l];
	// cout << "ANSWER";
	// cout << s << ' ' << t << endl;
	answer(s,t);
}
/*
10 17 13 30 5 2
1 0
2 0
3 1
4 0
5 1
6 1
7 1
8 3
9 0
9 7
9 3
3 2
8 6
6 2
8 2
8 1
4 3
*/
/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/
/*
11 12 16 19 9 10
1 0
2 0
3 1
4 0
5 4
6 3
7 4
8 4
9 5
10 1
9 3
5 1
*/

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4988 KB	Output is correct
2	Correct	3 ms	5004 KB	Output is correct
3	Correct	3 ms	4944 KB	Output is correct
4	Correct	3 ms	5000 KB	Output is correct
5	Correct	3 ms	4944 KB	Output is correct
6	Correct	3 ms	4944 KB	Output is correct
7	Correct	2 ms	4944 KB	Output is correct
8	Correct	3 ms	4944 KB	Output is correct
9	Correct	4 ms	5000 KB	Output is correct
10	Correct	4 ms	5000 KB	Output is correct
11	Correct	3 ms	4996 KB	Output is correct
12	Correct	4 ms	4996 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5072 KB	Output is correct
2	Correct	13 ms	5808 KB	Output is correct
3	Correct	156 ms	12764 KB	Output is correct
4	Correct	131 ms	12884 KB	Output is correct
5	Correct	117 ms	12648 KB	Output is correct
6	Correct	99 ms	12640 KB	Output is correct
7	Correct	117 ms	12640 KB	Output is correct
8	Correct	130 ms	12652 KB	Output is correct
9	Correct	102 ms	12664 KB	Output is correct
10	Correct	110 ms	12652 KB	Output is correct
11	Correct	117 ms	11924 KB	Output is correct
12	Correct	133 ms	12032 KB	Output is correct
13	Correct	144 ms	12156 KB	Output is correct
14	Correct	162 ms	12028 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	5712 KB	Output is correct
2	Correct	21 ms	6468 KB	Output is correct
3	Correct	36 ms	7332 KB	Output is correct
4	Correct	116 ms	11924 KB	Output is correct
5	Correct	91 ms	11920 KB	Output is correct
6	Correct	86 ms	12036 KB	Output is correct
7	Correct	130 ms	12028 KB	Output is correct
8	Correct	134 ms	11772 KB	Output is correct
9	Correct	78 ms	11964 KB	Output is correct

Subtask #4

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5072 KB	Output is correct
2	Correct	14 ms	5836 KB	Output is correct
3	Correct	72 ms	10956 KB	Output is correct
4	Correct	121 ms	12648 KB	Output is correct
5	Correct	105 ms	12648 KB	Output is correct
6	Correct	134 ms	12644 KB	Output is correct
7	Correct	117 ms	12644 KB	Output is correct
8	Correct	138 ms	12704 KB	Output is correct
9	Correct	160 ms	12624 KB	Output is correct
10	Correct	138 ms	12648 KB	Output is correct
11	Correct	134 ms	12040 KB	Output is correct
12	Correct	140 ms	12012 KB	Output is correct
13	Correct	172 ms	12024 KB	Output is correct
14	Correct	175 ms	11772 KB	Output is correct
15	Correct	150 ms	12732 KB	Output is correct
16	Correct	111 ms	12660 KB	Output is correct
17	Correct	175 ms	12140 KB	Output is correct
18	Correct	136 ms	12028 KB	Output is correct
19	Correct	108 ms	12660 KB	Output is correct
20	Correct	138 ms	12036 KB	Output is correct
21	Correct	86 ms	13484 KB	Output is correct
22	Correct	102 ms	13276 KB	Output is correct
23	Correct	131 ms	12808 KB	Output is correct
24	Correct	132 ms	12684 KB	Output is correct
25	Correct	162 ms	12120 KB	Output is correct

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	5844 KB	Output is correct
2	Correct	20 ms	5960 KB	Output is correct
3	Correct	141 ms	13092 KB	Output is correct
4	Correct	151 ms	13280 KB	Output is correct
5	Correct	203 ms	14376 KB	Output is correct
6	Correct	204 ms	14088 KB	Output is correct
7	Correct	206 ms	14088 KB	Output is correct
8	Correct	206 ms	14132 KB	Output is correct
9	Correct	149 ms	11300 KB	Output is correct
10	Correct	123 ms	11736 KB	Output is correct
11	Correct	167 ms	12316 KB	Output is correct
12	Correct	195 ms	13520 KB	Output is correct
13	Correct	147 ms	13928 KB	Output is correct
14	Correct	198 ms	14116 KB	Output is correct
15	Correct	145 ms	14124 KB	Output is correct
16	Correct	171 ms	12336 KB	Output is correct
17	Correct	106 ms	12836 KB	Output is correct
18	Correct	127 ms	13020 KB	Output is correct
19	Correct	123 ms	12936 KB	Output is correct
20	Correct	106 ms	13084 KB	Output is correct
21	Correct	181 ms	14424 KB	Output is correct

Subtask #6

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	5732 KB	Output is correct
2	Correct	21 ms	5912 KB	Output is correct
3	Correct	160 ms	12800 KB	Output is correct
4	Correct	122 ms	12960 KB	Output is correct
5	Correct	139 ms	13208 KB	Output is correct
6	Correct	170 ms	14080 KB	Output is correct
7	Correct	141 ms	13056 KB	Output is correct
8	Correct	167 ms	13176 KB	Output is correct
9	Correct	119 ms	13136 KB	Output is correct
10	Correct	205 ms	14096 KB	Output is correct
11	Correct	205 ms	14236 KB	Output is correct
12	Correct	230 ms	14096 KB	Output is correct
13	Correct	111 ms	12316 KB	Output is correct
14	Correct	147 ms	11728 KB	Output is correct
15	Correct	117 ms	12324 KB	Output is correct
16	Correct	122 ms	11652 KB	Output is correct
17	Correct	126 ms	12364 KB	Output is correct
18	Correct	119 ms	11756 KB	Output is correct
19	Correct	144 ms	13424 KB	Output is correct
20	Correct	155 ms	13760 KB	Output is correct
21	Correct	175 ms	14104 KB	Output is correct
22	Correct	171 ms	14080 KB	Output is correct
23	Correct	152 ms	14252 KB	Output is correct
24	Correct	212 ms	14172 KB	Output is correct
25	Correct	167 ms	14080 KB	Output is correct
26	Correct	158 ms	14104 KB	Output is correct
27	Correct	129 ms	13312 KB	Output is correct
28	Correct	95 ms	12868 KB	Output is correct
29	Correct	100 ms	13096 KB	Output is correct
30	Correct	98 ms	12964 KB	Output is correct
31	Correct	126 ms	12956 KB	Output is correct
32	Correct	142 ms	12848 KB	Output is correct
33	Correct	141 ms	13204 KB	Output is correct
34	Correct	105 ms	13024 KB	Output is correct
35	Correct	146 ms	12956 KB	Output is correct
36	Correct	112 ms	12868 KB	Output is correct
37	Correct	109 ms	13032 KB	Output is correct
38	Correct	153 ms	13324 KB	Output is correct
39	Correct	201 ms	14456 KB	Output is correct
40	Correct	167 ms	14368 KB	Output is correct
41	Correct	198 ms	14516 KB	Output is correct
42	Correct	167 ms	14084 KB	Output is correct