oj.uz

답안 #725667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725667 2023-04-17T20:35:07 Z FatihSolak 통행료 (IOI18_highway) C++17
100 / 100
 230 ms 14516 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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