답안 #75245 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75245	2018-09-08T22:11:50 Z	Xellos	통행료 (IOI18_highway)	C++14	100 / 100	664 ms	20328 KB

highway

#include <bits/stdc++.h>
#define ff first
#define ss second
#include "highway.h"
using namespace std;

using cat = long long;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  vector<int> vq(M, 1);
  cat L = ask(vq) / B;
  // find edge on shortest path
  int el = 0, er = M;
  while(er - el > 1) {
  	int em = (el + er + 1) / 2;
  	for(int i = 0; i < em; i++) vq[i] = 0;
  	for(int i = em; i < M; i++) vq[i] = 1;
  	cat ans = ask(vq);
  	if(ans == L * A) er = em;
  	else el = em;
  }
  vector< vector< pair<int, int> > > G(N);
  for(int i = 0; i <= el; i++) {
  	G[U[i]].push_back({V[i], i});
  	G[V[i]].push_back({U[i], i});
  }
  // BFS graph for 2
  queue<int> q;
  vector<int> dep2(N, -1), v2;
  vector< vector<int> > e2_in(N);
  q.push(U[el]);
  dep2[U[el]] = 0;
  while(!q.empty()) {
  	v2.push_back(q.front());
  	for(auto e: G[q.front()]) if(dep2[e.ff] == -1) {
  		dep2[e.ff] = dep2[q.front()]+1;
  		q.push(e.ff);
  	}
  	q.pop();
  }
  for(int i = 0; i <= el; i++) {
  	if(dep2[U[i]] > dep2[V[i]]) e2_in[U[i]].push_back(i);
  	if(dep2[U[i]] < dep2[V[i]]) e2_in[V[i]].push_back(i);
  }
  int v2l = 0, v2r = v2.size();
  while(dep2[v2[v2r-1]] > L) v2r--;
  while(v2r-v2l > 1) {
  	int v2m = (v2l + v2r + 1) / 2;
  	for(int i = 0; i < M; i++) vq[i] = 1;
  	for(int i = 0; i < v2m; i++)
  		for(auto e: e2_in[v2[i]]) vq[e] = 0;
  	cat ans = ask(vq);
  	if(ans == L * A) v2r = v2m;
  	else v2l = v2m;
  }
  int S = v2[v2l];
  vector<bool> bl(N, false);
  vector<int> e_bl;
  int cur = S;
  while(dep2[cur] > 0) {
	bl[cur] = true;
  	for(auto e: G[cur]) if(dep2[e.ff] == dep2[cur]-1) {
  		e_bl.push_back(e.ss);
  		cur = e.ff;
  		break;
  	}
  }
  // BFS graph for 1
  vector<int> dep1(N, -1), v1;
  vector< vector<int> > e1_in(N);
  q.push(U[el]);
  dep1[U[el]] = 0;
  while(!q.empty()) {
  	v1.push_back(q.front());
  	for(auto e: G[q.front()]) if(!bl[e.ff] && dep1[e.ff] == -1) {
  		dep1[e.ff] = dep1[q.front()]+1;
  		q.push(e.ff);
  	}
  	q.pop();
  }
  for(int i = 0; i <= el; i++) if(!bl[U[i]] && !bl[V[i]]) {
  	if(dep1[U[i]] > dep1[V[i]]) e1_in[U[i]].push_back(i);
  	if(dep1[U[i]] < dep1[V[i]]) e1_in[V[i]].push_back(i);
  }
  int v1l = 0, v1r = v1.size();
  while(dep1[v1[v1r-1]] > L-dep2[S]) v1r--;
  while(v1r-v1l > 1) {
  	int v1m = (v1l + v1r + 1) / 2;
  	for(int i = 0; i < M; i++) vq[i] = 1;
  	for(auto e: e_bl) vq[e] = 0;
  	for(int i = 0; i < v1m; i++)
  		for(auto e: e1_in[v1[i]]) vq[e] = 0;
  	cat ans = ask(vq);
  	if(ans == L * A) v1r = v1m;
  	else v1l = v1m;
  }
  int T = v1[v1l];
  answer(S, T);
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	416 KB	Output is correct
2	Correct	2 ms	320 KB	Output is correct
3	Correct	2 ms	380 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	316 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	248 KB	Output is correct
9	Correct	2 ms	248 KB	Output is correct
10	Correct	2 ms	324 KB	Output is correct
11	Correct	8 ms	248 KB	Output is correct
12	Correct	2 ms	248 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	22 ms	1696 KB	Output is correct
3	Correct	336 ms	15160 KB	Output is correct
4	Correct	377 ms	15124 KB	Output is correct
5	Correct	275 ms	15012 KB	Output is correct
6	Correct	333 ms	14252 KB	Output is correct
7	Correct	241 ms	14724 KB	Output is correct
8	Correct	215 ms	13360 KB	Output is correct
9	Correct	247 ms	14960 KB	Output is correct
10	Correct	353 ms	14940 KB	Output is correct
11	Correct	204 ms	13248 KB	Output is correct
12	Correct	260 ms	13748 KB	Output is correct
13	Correct	279 ms	15308 KB	Output is correct
14	Correct	284 ms	14876 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	1276 KB	Output is correct
2	Correct	37 ms	2820 KB	Output is correct
3	Correct	50 ms	4964 KB	Output is correct
4	Correct	148 ms	12748 KB	Output is correct
5	Correct	151 ms	11344 KB	Output is correct
6	Correct	185 ms	14648 KB	Output is correct
7	Correct	186 ms	14836 KB	Output is correct
8	Correct	140 ms	13292 KB	Output is correct
9	Correct	161 ms	13744 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	508 KB	Output is correct
2	Correct	22 ms	1656 KB	Output is correct
3	Correct	161 ms	11748 KB	Output is correct
4	Correct	216 ms	14480 KB	Output is correct
5	Correct	222 ms	18304 KB	Output is correct
6	Correct	221 ms	14376 KB	Output is correct
7	Correct	166 ms	11484 KB	Output is correct
8	Correct	198 ms	14544 KB	Output is correct
9	Correct	427 ms	16224 KB	Output is correct
10	Correct	259 ms	13880 KB	Output is correct
11	Correct	355 ms	15284 KB	Output is correct
12	Correct	471 ms	15828 KB	Output is correct
13	Correct	393 ms	14308 KB	Output is correct
14	Correct	339 ms	15144 KB	Output is correct
15	Correct	163 ms	13860 KB	Output is correct
16	Correct	225 ms	16548 KB	Output is correct
17	Correct	329 ms	15144 KB	Output is correct
18	Correct	296 ms	15244 KB	Output is correct
19	Correct	137 ms	11392 KB	Output is correct
20	Correct	160 ms	12148 KB	Output is correct
21	Correct	236 ms	13028 KB	Output is correct
22	Correct	363 ms	17104 KB	Output is correct
23	Correct	337 ms	17404 KB	Output is correct
24	Correct	405 ms	17460 KB	Output is correct
25	Correct	505 ms	15824 KB	Output is correct

Subtask #5
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	2064 KB	Output is correct
2	Correct	56 ms	2352 KB	Output is correct
3	Correct	290 ms	19216 KB	Output is correct
4	Correct	322 ms	16300 KB	Output is correct
5	Correct	278 ms	16356 KB	Output is correct
6	Correct	318 ms	19544 KB	Output is correct
7	Correct	316 ms	20232 KB	Output is correct
8	Correct	317 ms	18932 KB	Output is correct
9	Correct	204 ms	5444 KB	Output is correct
10	Correct	224 ms	8724 KB	Output is correct
11	Correct	301 ms	11484 KB	Output is correct
12	Correct	318 ms	17088 KB	Output is correct
13	Correct	306 ms	17264 KB	Output is correct
14	Correct	353 ms	20180 KB	Output is correct
15	Correct	371 ms	20000 KB	Output is correct
16	Correct	297 ms	11864 KB	Output is correct
17	Correct	329 ms	15716 KB	Output is correct
18	Correct	369 ms	15420 KB	Output is correct
19	Correct	477 ms	18464 KB	Output is correct
20	Correct	262 ms	15340 KB	Output is correct
21	Correct	352 ms	20320 KB	Output is correct

Subtask #6
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	2208 KB	Output is correct
2	Correct	33 ms	2092 KB	Output is correct
3	Correct	268 ms	18944 KB	Output is correct
4	Correct	334 ms	18952 KB	Output is correct
5	Correct	307 ms	19176 KB	Output is correct
6	Correct	336 ms	19872 KB	Output is correct
7	Correct	256 ms	18996 KB	Output is correct
8	Correct	248 ms	18392 KB	Output is correct
9	Correct	242 ms	16040 KB	Output is correct
10	Correct	346 ms	20328 KB	Output is correct
11	Correct	521 ms	20260 KB	Output is correct
12	Correct	317 ms	18584 KB	Output is correct
13	Correct	214 ms	6296 KB	Output is correct
14	Correct	217 ms	4916 KB	Output is correct
15	Correct	189 ms	7320 KB	Output is correct
16	Correct	247 ms	9044 KB	Output is correct
17	Correct	335 ms	11028 KB	Output is correct
18	Correct	234 ms	6424 KB	Output is correct
19	Correct	299 ms	15796 KB	Output is correct
20	Correct	270 ms	18564 KB	Output is correct
21	Correct	357 ms	20028 KB	Output is correct
22	Correct	394 ms	19932 KB	Output is correct
23	Correct	331 ms	19956 KB	Output is correct
24	Correct	426 ms	20080 KB	Output is correct
25	Correct	287 ms	19612 KB	Output is correct
26	Correct	437 ms	19800 KB	Output is correct
27	Correct	304 ms	13628 KB	Output is correct
28	Correct	253 ms	15556 KB	Output is correct
29	Correct	207 ms	13068 KB	Output is correct
30	Correct	371 ms	14712 KB	Output is correct
31	Correct	338 ms	15624 KB	Output is correct
32	Correct	430 ms	15924 KB	Output is correct
33	Correct	331 ms	14344 KB	Output is correct
34	Correct	343 ms	14376 KB	Output is correct
35	Correct	232 ms	16232 KB	Output is correct
36	Correct	232 ms	13080 KB	Output is correct
37	Correct	256 ms	14384 KB	Output is correct
38	Correct	238 ms	12904 KB	Output is correct
39	Correct	362 ms	19760 KB	Output is correct
40	Correct	350 ms	19680 KB	Output is correct
41	Correct	664 ms	20184 KB	Output is correct
42	Correct	367 ms	20276 KB	Output is correct

답안 #75245

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