답안 #75236 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75236	2018-09-08T18:06:20 Z	ainta	통행료 (IOI18_highway)	C++17	90 / 100	361 ms	11496 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;
		if (e - b > 60000)mid = 60000;
		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	3904 KB	Output is correct
2	Correct	5 ms	3864 KB	Output is correct
3	Correct	5 ms	3868 KB	Output is correct
4	Correct	5 ms	3832 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	3868 KB	Output is correct
8	Correct	5 ms	3864 KB	Output is correct
9	Correct	5 ms	3860 KB	Output is correct
10	Correct	5 ms	3868 KB	Output is correct
11	Correct	5 ms	3960 KB	Output is correct
12	Correct	5 ms	3832 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4000 KB	Output is correct
2	Correct	21 ms	4568 KB	Output is correct
3	Correct	237 ms	10092 KB	Output is correct
4	Correct	247 ms	10036 KB	Output is correct
5	Correct	273 ms	10028 KB	Output is correct
6	Correct	240 ms	10076 KB	Output is correct
7	Correct	221 ms	10088 KB	Output is correct
8	Correct	213 ms	10000 KB	Output is correct
9	Correct	205 ms	10032 KB	Output is correct
10	Correct	227 ms	10068 KB	Output is correct
11	Correct	205 ms	10264 KB	Output is correct
12	Correct	228 ms	10308 KB	Output is correct
13	Correct	237 ms	10312 KB	Output is correct
14	Correct	262 ms	10248 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	4564 KB	Output is correct
2	Correct	40 ms	5228 KB	Output is correct
3	Correct	56 ms	5880 KB	Output is correct
4	Correct	161 ms	9988 KB	Output is correct
5	Correct	153 ms	9972 KB	Output is correct
6	Correct	167 ms	10108 KB	Output is correct
7	Correct	160 ms	9944 KB	Output is correct
8	Correct	178 ms	10008 KB	Output is correct
9	Correct	169 ms	9896 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3960 KB	Output is correct
2	Correct	25 ms	4520 KB	Output is correct
3	Correct	145 ms	8652 KB	Output is correct
4	Correct	217 ms	10124 KB	Output is correct
5	Correct	187 ms	10004 KB	Output is correct
6	Correct	195 ms	10000 KB	Output is correct
7	Correct	222 ms	10008 KB	Output is correct
8	Correct	195 ms	10084 KB	Output is correct
9	Correct	244 ms	10160 KB	Output is correct
10	Correct	243 ms	10060 KB	Output is correct
11	Correct	263 ms	10228 KB	Output is correct
12	Correct	293 ms	10228 KB	Output is correct
13	Correct	208 ms	10248 KB	Output is correct
14	Correct	205 ms	10228 KB	Output is correct
15	Correct	171 ms	10016 KB	Output is correct
16	Correct	168 ms	10000 KB	Output is correct
17	Correct	237 ms	10232 KB	Output is correct
18	Correct	241 ms	10248 KB	Output is correct
19	Correct	216 ms	10016 KB	Output is correct
20	Correct	204 ms	10244 KB	Output is correct
21	Correct	219 ms	10368 KB	Output is correct
22	Correct	203 ms	10268 KB	Output is correct
23	Correct	224 ms	10580 KB	Output is correct
24	Correct	248 ms	10568 KB	Output is correct
25	Correct	280 ms	10288 KB	Output is correct

Subtask #5
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	4532 KB	Output is correct
2	Correct	30 ms	4620 KB	Output is correct
3	Correct	239 ms	10444 KB	Output is correct
4	Correct	288 ms	10512 KB	Output is correct
5	Correct	343 ms	10992 KB	Output is correct
6	Correct	323 ms	11036 KB	Output is correct
7	Correct	302 ms	10996 KB	Output is correct
8	Correct	355 ms	11000 KB	Output is correct
9	Correct	285 ms	8740 KB	Output is correct
10	Correct	227 ms	8904 KB	Output is correct
11	Correct	269 ms	9020 KB	Output is correct
12	Correct	291 ms	10356 KB	Output is correct
13	Correct	326 ms	10648 KB	Output is correct
14	Correct	340 ms	10876 KB	Output is correct
15	Correct	335 ms	10864 KB	Output is correct
16	Correct	296 ms	9416 KB	Output is correct
17	Correct	263 ms	10396 KB	Output is correct
18	Correct	280 ms	10472 KB	Output is correct
19	Correct	291 ms	10516 KB	Output is correct
20	Correct	186 ms	10536 KB	Output is correct
21	Correct	313 ms	11400 KB	Output is correct

Subtask #6
21.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	4572 KB	Output is correct
2	Correct	33 ms	4608 KB	Output is correct
3	Correct	205 ms	10376 KB	Output is correct
4	Correct	233 ms	10376 KB	Output is correct
5	Correct	295 ms	10576 KB	Output is correct
6	Correct	348 ms	11000 KB	Output is correct
7	Correct	235 ms	10364 KB	Output is correct
8	Correct	239 ms	10360 KB	Output is correct
9	Correct	237 ms	10572 KB	Output is correct
10	Correct	326 ms	10992 KB	Output is correct
11	Correct	284 ms	11060 KB	Output is correct
12	Correct	312 ms	10984 KB	Output is correct
13	Correct	295 ms	9028 KB	Output is correct
14	Correct	261 ms	8864 KB	Output is correct
15	Correct	275 ms	9132 KB	Output is correct
16	Correct	209 ms	8948 KB	Output is correct
17	Correct	296 ms	9060 KB	Output is correct
18	Correct	216 ms	8948 KB	Output is correct
19	Correct	301 ms	10328 KB	Output is correct
20	Correct	300 ms	10536 KB	Output is correct
21	Correct	320 ms	10900 KB	Output is correct
22	Correct	320 ms	10852 KB	Output is correct
23	Correct	311 ms	10896 KB	Output is correct
24	Correct	274 ms	10848 KB	Output is correct
25	Correct	284 ms	10860 KB	Output is correct
26	Correct	300 ms	10856 KB	Output is correct
27	Correct	239 ms	10484 KB	Output is correct
28	Correct	225 ms	10480 KB	Output is correct
29	Correct	295 ms	10652 KB	Output is correct
30	Correct	181 ms	10492 KB	Output is correct
31	Correct	211 ms	10528 KB	Output is correct
32	Correct	236 ms	10392 KB	Output is correct
33	Correct	276 ms	10560 KB	Output is correct
34	Correct	256 ms	10572 KB	Output is correct
35	Correct	228 ms	10464 KB	Output is correct
36	Correct	229 ms	10408 KB	Output is correct
37	Correct	240 ms	10724 KB	Output is correct
38	Correct	231 ms	10536 KB	Output is correct
39	Correct	277 ms	11424 KB	Output is correct
40	Correct	297 ms	11412 KB	Output is correct
41	Partially correct	361 ms	11424 KB	Output is partially correct
42	Correct	293 ms	11496 KB	Output is correct

답안 #75236

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