답안 #77104 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77104	2018-09-21T11:59:16 Z	gs14004	통행료 (IOI18_highway)	C++17	100 / 100	336 ms	9956 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 90005;

int dist[MAXN];
vector<int> gph[MAXN];

lint cut_ask(int m, vector<int> &c, vector<int> &u, vector<int> &v){
	bitset<MAXN> vis;
	for(auto &i : c) vis[i] = 1;
	vector<int> query(m);
	for(int i=0; i<m; i++){
		if(vis[u[i]] != vis[v[i]]) query[i] = 1;
	}
	return ask(query);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	for(int i=0; i<M; i++){
		gph[U[i]].emplace_back(V[i]);
		gph[V[i]].emplace_back(U[i]); 
	}
	vector<int> v(M);
	int stdist = ask(v) / A;
	int s = 0, e = M - 1;
	while(s != e){
		int m = (s + e) / 2;
		fill(v.begin() + m + 1, v.end(), 0);
		fill(v.begin(), v.begin() + m + 1, 1);
		if(ask(v) != 1ll * A * stdist) e = m; // encloses all spaths
		else s = m + 1;
	}
	// 18 queries till this point
	vector<int> bord[2];
	queue<pi> que;
	que.emplace(0, U[s]);
	que.emplace(1, V[s]);
	memset(dist, 0x3f, sizeof(dist));
	dist[U[s]] = dist[V[s]] = 0;
	while(!que.empty()){
		auto x = que.front(); que.pop();
		bord[x.first].push_back(x.second);
		for(auto &i : gph[x.second]){
			if(dist[i] > dist[x.second] + 1){
				dist[i] = dist[x.second] + 1;
				que.emplace(x.first, i);
			}
		}
	}
	s = 0, e = (int)bord[0].size() - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		vector<int> C(bord[0].begin() + m, bord[0].end());
		if(cut_ask(M, C, U, V) != 1ll * stdist * A) s = m;
		else e = m - 1;
	}
	int S = bord[0][s];
	s = 0, e = (int)bord[1].size() - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		vector<int> C(bord[1].begin() + m, bord[1].end());
		if(cut_ask(M, C, U, V) != 1ll * stdist * A) s = m;
		else e = m - 1;
	}
	int T = bord[1][s];
	answer(S, T);
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2708 KB	Output is correct
2	Correct	5 ms	2732 KB	Output is correct
3	Correct	4 ms	2736 KB	Output is correct
4	Correct	4 ms	2696 KB	Output is correct
5	Correct	5 ms	2780 KB	Output is correct
6	Correct	4 ms	2680 KB	Output is correct
7	Correct	4 ms	2784 KB	Output is correct
8	Correct	5 ms	2708 KB	Output is correct
9	Correct	4 ms	2728 KB	Output is correct
10	Correct	4 ms	2728 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2692 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2824 KB	Output is correct
2	Correct	26 ms	3404 KB	Output is correct
3	Correct	200 ms	8512 KB	Output is correct
4	Correct	193 ms	8484 KB	Output is correct
5	Correct	203 ms	8468 KB	Output is correct
6	Correct	201 ms	8412 KB	Output is correct
7	Correct	203 ms	8476 KB	Output is correct
8	Correct	234 ms	8696 KB	Output is correct
9	Correct	198 ms	8632 KB	Output is correct
10	Correct	194 ms	8472 KB	Output is correct
11	Correct	202 ms	8308 KB	Output is correct
12	Correct	202 ms	8356 KB	Output is correct
13	Correct	230 ms	8248 KB	Output is correct
14	Correct	188 ms	8444 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	3324 KB	Output is correct
2	Correct	36 ms	4080 KB	Output is correct
3	Correct	67 ms	4680 KB	Output is correct
4	Correct	123 ms	8248 KB	Output is correct
5	Correct	181 ms	8328 KB	Output is correct
6	Correct	180 ms	8244 KB	Output is correct
7	Correct	183 ms	8480 KB	Output is correct
8	Correct	168 ms	8248 KB	Output is correct
9	Correct	152 ms	8372 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2824 KB	Output is correct
2	Correct	25 ms	3448 KB	Output is correct
3	Correct	156 ms	7328 KB	Output is correct
4	Correct	212 ms	8560 KB	Output is correct
5	Correct	189 ms	8592 KB	Output is correct
6	Correct	210 ms	8676 KB	Output is correct
7	Correct	209 ms	8636 KB	Output is correct
8	Correct	202 ms	8580 KB	Output is correct
9	Correct	184 ms	8596 KB	Output is correct
10	Correct	214 ms	8544 KB	Output is correct
11	Correct	196 ms	8448 KB	Output is correct
12	Correct	188 ms	8336 KB	Output is correct
13	Correct	196 ms	8268 KB	Output is correct
14	Correct	205 ms	8320 KB	Output is correct
15	Correct	207 ms	8596 KB	Output is correct
16	Correct	211 ms	8648 KB	Output is correct
17	Correct	193 ms	8324 KB	Output is correct
18	Correct	210 ms	8368 KB	Output is correct
19	Correct	190 ms	8596 KB	Output is correct
20	Correct	208 ms	8444 KB	Output is correct
21	Correct	163 ms	9240 KB	Output is correct
22	Correct	172 ms	9208 KB	Output is correct
23	Correct	187 ms	9024 KB	Output is correct
24	Correct	208 ms	8892 KB	Output is correct
25	Correct	211 ms	8344 KB	Output is correct

Subtask #5
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	3460 KB	Output is correct
2	Correct	41 ms	3424 KB	Output is correct
3	Correct	194 ms	8680 KB	Output is correct
4	Correct	253 ms	9048 KB	Output is correct
5	Correct	292 ms	9956 KB	Output is correct
6	Correct	310 ms	9620 KB	Output is correct
7	Correct	306 ms	9640 KB	Output is correct
8	Correct	287 ms	9608 KB	Output is correct
9	Correct	273 ms	7872 KB	Output is correct
10	Correct	255 ms	8352 KB	Output is correct
11	Correct	259 ms	8428 KB	Output is correct
12	Correct	301 ms	9308 KB	Output is correct
13	Correct	289 ms	9596 KB	Output is correct
14	Correct	292 ms	9544 KB	Output is correct
15	Correct	300 ms	9700 KB	Output is correct
16	Correct	271 ms	8624 KB	Output is correct
17	Correct	197 ms	9156 KB	Output is correct
18	Correct	196 ms	9448 KB	Output is correct
19	Correct	213 ms	9180 KB	Output is correct
20	Correct	195 ms	9488 KB	Output is correct
21	Correct	290 ms	9580 KB	Output is correct

Subtask #6
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	3484 KB	Output is correct
2	Correct	30 ms	3496 KB	Output is correct
3	Correct	235 ms	8848 KB	Output is correct
4	Correct	231 ms	9108 KB	Output is correct
5	Correct	264 ms	9320 KB	Output is correct
6	Correct	290 ms	9620 KB	Output is correct
7	Correct	222 ms	8932 KB	Output is correct
8	Correct	257 ms	9104 KB	Output is correct
9	Correct	239 ms	9176 KB	Output is correct
10	Correct	308 ms	9668 KB	Output is correct
11	Correct	308 ms	9728 KB	Output is correct
12	Correct	314 ms	9640 KB	Output is correct
13	Correct	211 ms	8432 KB	Output is correct
14	Correct	271 ms	8328 KB	Output is correct
15	Correct	249 ms	8484 KB	Output is correct
16	Correct	228 ms	8368 KB	Output is correct
17	Correct	254 ms	8376 KB	Output is correct
18	Correct	261 ms	8388 KB	Output is correct
19	Correct	304 ms	9200 KB	Output is correct
20	Correct	280 ms	9516 KB	Output is correct
21	Correct	336 ms	9612 KB	Output is correct
22	Correct	325 ms	9532 KB	Output is correct
23	Correct	296 ms	9672 KB	Output is correct
24	Correct	281 ms	9484 KB	Output is correct
25	Correct	292 ms	9768 KB	Output is correct
26	Correct	287 ms	9776 KB	Output is correct
27	Correct	194 ms	9212 KB	Output is correct
28	Correct	194 ms	9352 KB	Output is correct
29	Correct	207 ms	9456 KB	Output is correct
30	Correct	190 ms	9004 KB	Output is correct
31	Correct	202 ms	9168 KB	Output is correct
32	Correct	218 ms	9320 KB	Output is correct
33	Correct	212 ms	9268 KB	Output is correct
34	Correct	218 ms	9376 KB	Output is correct
35	Correct	199 ms	9348 KB	Output is correct
36	Correct	196 ms	9296 KB	Output is correct
37	Correct	217 ms	9616 KB	Output is correct
38	Correct	174 ms	9352 KB	Output is correct
39	Correct	282 ms	9540 KB	Output is correct
40	Correct	256 ms	9660 KB	Output is correct
41	Correct	211 ms	9460 KB	Output is correct
42	Correct	264 ms	9504 KB	Output is correct

답안 #77104

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 6.0 / 6.0

Subtask #4 33.0 / 33.0

Subtask #5 18.0 / 18.0

Subtask #6 31.0 / 31.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
6.0 / 6.0

Subtask #4
33.0 / 33.0

Subtask #5
18.0 / 18.0

Subtask #6
31.0 / 31.0