답안 #75235 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75235	2018-09-08T17:58:01 Z	ainta	통행료 (IOI18_highway)	C++17	90 / 100	391 ms	11484 KB

highway

#include "highway.h"
#include <cstdio>
#include <algorithm>
#define N_ 151000
using namespace std;
int n, m, Q[N_], head, tail, par[N_], vis[N_], pN[N_], vv[N_];
vector<int>T, E[N_];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int i;
	n = N;
	m = U.size();
	T.resize(m);
	for (i = 0; i < m; i++) {
		T[i] = 0;
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
	}
	long long L = ask(T);
	int b = 0, e = n - 2, mid, r = n - 1;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < m; i++) {
			if (U[i] > mid || V[i] > mid)T[i] = 1;
			else T[i] = 0;
		}
		if (ask(T) == L)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	int root = r;
	Q[++tail] = root, vis[root] = 1;
	par[root] = -1;
	while (head < tail) {
		int x = Q[++head];
		for (auto &y : E[x]) {
			if (!vis[y]) {
				vis[y] = 1;
				Q[++tail] = y;
				par[y] = x;
			}
		}
	}
	for (i = 0; i < m; i++) {
		if (par[U[i]] == V[i])pN[U[i]] = i;
		if (par[V[i]] == U[i])pN[V[i]] = i;
	}
	b = 1, e = tail - 1, r = tail;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < m; i++)T[i] = 1;
		for (i = 2; i <= mid; i++) T[pN[Q[i]]] = 0;
		if (ask(T) == L)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	int ed = Q[r];
	int tp = ed;
	while (tp != root) {
		vv[pN[tp]] = 1;
		tp = par[tp];
	}
	b = 1, e = r - 1;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < m; i++) {
			if(!vv[i])T[i] = 1;
			else T[i] = 0;
		}
		for (i = 2; i <= mid; i++) T[pN[Q[i]]] = 0;
		if (ask(T) == L)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	int st = Q[r];
	answer(st, ed);
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3880 KB	Output is correct
2	Correct	5 ms	3832 KB	Output is correct
3	Correct	5 ms	3864 KB	Output is correct
4	Correct	5 ms	3868 KB	Output is correct
5	Correct	5 ms	3832 KB	Output is correct
6	Correct	5 ms	3880 KB	Output is correct
7	Correct	5 ms	3832 KB	Output is correct
8	Correct	5 ms	3832 KB	Output is correct
9	Correct	6 ms	3832 KB	Output is correct
10	Correct	5 ms	3832 KB	Output is correct
11	Correct	5 ms	3864 KB	Output is correct
12	Correct	5 ms	3864 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3832 KB	Output is correct
2	Correct	19 ms	4516 KB	Output is correct
3	Correct	229 ms	10072 KB	Output is correct
4	Correct	251 ms	10052 KB	Output is correct
5	Correct	244 ms	10160 KB	Output is correct
6	Correct	248 ms	10104 KB	Output is correct
7	Correct	205 ms	10040 KB	Output is correct
8	Correct	222 ms	10008 KB	Output is correct
9	Correct	197 ms	10040 KB	Output is correct
10	Correct	278 ms	10096 KB	Output is correct
11	Correct	198 ms	10312 KB	Output is correct
12	Correct	234 ms	10228 KB	Output is correct
13	Correct	217 ms	10248 KB	Output is correct
14	Correct	297 ms	10340 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	4520 KB	Output is correct
2	Correct	53 ms	5208 KB	Output is correct
3	Correct	60 ms	5880 KB	Output is correct
4	Correct	157 ms	9936 KB	Output is correct
5	Correct	164 ms	9896 KB	Output is correct
6	Correct	162 ms	10120 KB	Output is correct
7	Correct	182 ms	9996 KB	Output is correct
8	Correct	185 ms	10008 KB	Output is correct
9	Correct	164 ms	9904 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3912 KB	Output is correct
2	Correct	18 ms	4508 KB	Output is correct
3	Correct	143 ms	8640 KB	Output is correct
4	Correct	198 ms	10000 KB	Output is correct
5	Correct	202 ms	9992 KB	Output is correct
6	Correct	198 ms	10008 KB	Output is correct
7	Correct	211 ms	9988 KB	Output is correct
8	Correct	213 ms	10004 KB	Output is correct
9	Correct	240 ms	10076 KB	Output is correct
10	Correct	221 ms	10132 KB	Output is correct
11	Correct	267 ms	10232 KB	Output is correct
12	Correct	267 ms	10240 KB	Output is correct
13	Correct	259 ms	10340 KB	Output is correct
14	Correct	250 ms	10232 KB	Output is correct
15	Correct	210 ms	9992 KB	Output is correct
16	Correct	195 ms	9996 KB	Output is correct
17	Correct	257 ms	10228 KB	Output is correct
18	Correct	238 ms	10244 KB	Output is correct
19	Correct	193 ms	10068 KB	Output is correct
20	Correct	218 ms	10236 KB	Output is correct
21	Correct	209 ms	10272 KB	Output is correct
22	Correct	178 ms	10276 KB	Output is correct
23	Correct	224 ms	10668 KB	Output is correct
24	Correct	227 ms	10572 KB	Output is correct
25	Correct	268 ms	10288 KB	Output is correct

Subtask #5
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	4576 KB	Output is correct
2	Correct	23 ms	4604 KB	Output is correct
3	Correct	258 ms	10236 KB	Output is correct
4	Correct	278 ms	10552 KB	Output is correct
5	Correct	269 ms	10972 KB	Output is correct
6	Correct	324 ms	11020 KB	Output is correct
7	Correct	306 ms	11048 KB	Output is correct
8	Correct	363 ms	11060 KB	Output is correct
9	Correct	278 ms	8704 KB	Output is correct
10	Correct	252 ms	8904 KB	Output is correct
11	Correct	231 ms	9032 KB	Output is correct
12	Correct	276 ms	10360 KB	Output is correct
13	Correct	346 ms	10736 KB	Output is correct
14	Correct	341 ms	10884 KB	Output is correct
15	Correct	357 ms	10888 KB	Output is correct
16	Correct	233 ms	9416 KB	Output is correct
17	Correct	262 ms	10372 KB	Output is correct
18	Correct	236 ms	10460 KB	Output is correct
19	Correct	244 ms	10512 KB	Output is correct
20	Correct	237 ms	10544 KB	Output is correct
21	Correct	273 ms	11384 KB	Output is correct

Subtask #6
21.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	4576 KB	Output is correct
2	Correct	26 ms	4636 KB	Output is correct
3	Correct	257 ms	10304 KB	Output is correct
4	Correct	274 ms	10372 KB	Output is correct
5	Correct	274 ms	10508 KB	Output is correct
6	Correct	338 ms	11072 KB	Output is correct
7	Correct	238 ms	10276 KB	Output is correct
8	Correct	253 ms	10384 KB	Output is correct
9	Correct	236 ms	10476 KB	Output is correct
10	Correct	325 ms	10980 KB	Output is correct
11	Correct	277 ms	11032 KB	Output is correct
12	Correct	293 ms	11060 KB	Output is correct
13	Correct	304 ms	9020 KB	Output is correct
14	Correct	257 ms	8860 KB	Output is correct
15	Correct	273 ms	9020 KB	Output is correct
16	Correct	244 ms	8884 KB	Output is correct
17	Correct	308 ms	9024 KB	Output is correct
18	Correct	271 ms	8900 KB	Output is correct
19	Correct	299 ms	10324 KB	Output is correct
20	Correct	272 ms	10624 KB	Output is correct
21	Correct	318 ms	10876 KB	Output is correct
22	Correct	339 ms	10944 KB	Output is correct
23	Correct	321 ms	10920 KB	Output is correct
24	Correct	284 ms	10828 KB	Output is correct
25	Correct	278 ms	10852 KB	Output is correct
26	Correct	288 ms	10848 KB	Output is correct
27	Correct	232 ms	10504 KB	Output is correct
28	Correct	214 ms	10472 KB	Output is correct
29	Partially correct	242 ms	10740 KB	Output is partially correct
30	Correct	215 ms	10496 KB	Output is correct
31	Correct	192 ms	10532 KB	Output is correct
32	Correct	264 ms	10384 KB	Output is correct
33	Correct	242 ms	10672 KB	Output is correct
34	Correct	256 ms	10496 KB	Output is correct
35	Correct	229 ms	10436 KB	Output is correct
36	Correct	240 ms	10416 KB	Output is correct
37	Correct	231 ms	10704 KB	Output is correct
38	Correct	239 ms	10532 KB	Output is correct
39	Correct	290 ms	11484 KB	Output is correct
40	Correct	276 ms	11412 KB	Output is correct
41	Partially correct	391 ms	11416 KB	Output is partially correct
42	Correct	293 ms	11400 KB	Output is correct

답안 #75235

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 21.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
21.0 / 31.0