답안 #75237 :: oj.uz

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3908 KB	Output is correct
2	Correct	27 ms	4516 KB	Output is correct
3	Correct	219 ms	10044 KB	Output is correct
4	Correct	233 ms	10044 KB	Output is correct
5	Correct	290 ms	10048 KB	Output is correct
6	Correct	263 ms	10064 KB	Output is correct
7	Correct	222 ms	10024 KB	Output is correct
8	Correct	214 ms	10012 KB	Output is correct
9	Correct	192 ms	10028 KB	Output is correct
10	Correct	219 ms	10080 KB	Output is correct
11	Correct	231 ms	10232 KB	Output is correct
12	Correct	260 ms	10324 KB	Output is correct
13	Correct	227 ms	10244 KB	Output is correct
14	Correct	236 ms	10240 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	4548 KB	Output is correct
2	Correct	43 ms	5224 KB	Output is correct
3	Correct	47 ms	5880 KB	Output is correct
4	Correct	180 ms	9952 KB	Output is correct
5	Correct	177 ms	9900 KB	Output is correct
6	Correct	184 ms	10072 KB	Output is correct
7	Correct	173 ms	9896 KB	Output is correct
8	Correct	171 ms	10008 KB	Output is correct
9	Correct	154 ms	9900 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3920 KB	Output is correct
2	Correct	24 ms	4580 KB	Output is correct
3	Correct	142 ms	8660 KB	Output is correct
4	Correct	242 ms	10040 KB	Output is correct
5	Correct	214 ms	10008 KB	Output is correct
6	Correct	187 ms	10028 KB	Output is correct
7	Correct	205 ms	9992 KB	Output is correct
8	Correct	204 ms	10016 KB	Output is correct
9	Correct	279 ms	10052 KB	Output is correct
10	Correct	239 ms	10056 KB	Output is correct
11	Correct	251 ms	10228 KB	Output is correct
12	Correct	232 ms	10240 KB	Output is correct
13	Correct	248 ms	10224 KB	Output is correct
14	Correct	259 ms	10300 KB	Output is correct
15	Correct	211 ms	9988 KB	Output is correct
16	Correct	190 ms	9980 KB	Output is correct
17	Correct	259 ms	10240 KB	Output is correct
18	Correct	242 ms	10232 KB	Output is correct
19	Correct	202 ms	10076 KB	Output is correct
20	Correct	181 ms	10236 KB	Output is correct
21	Correct	200 ms	10180 KB	Output is correct
22	Correct	222 ms	10356 KB	Output is correct
23	Correct	220 ms	10568 KB	Output is correct
24	Correct	242 ms	10572 KB	Output is correct
25	Correct	301 ms	10276 KB	Output is correct

Subtask #5
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	4520 KB	Output is correct
2	Correct	30 ms	4600 KB	Output is correct
3	Correct	251 ms	10244 KB	Output is correct
4	Correct	270 ms	10484 KB	Output is correct
5	Correct	345 ms	11084 KB	Output is correct
6	Correct	308 ms	11160 KB	Output is correct
7	Correct	313 ms	10996 KB	Output is correct
8	Correct	321 ms	10972 KB	Output is correct
9	Correct	255 ms	8696 KB	Output is correct
10	Correct	240 ms	8900 KB	Output is correct
11	Correct	289 ms	9136 KB	Output is correct
12	Correct	276 ms	10340 KB	Output is correct
13	Correct	327 ms	10664 KB	Output is correct
14	Correct	333 ms	10916 KB	Output is correct
15	Correct	293 ms	10880 KB	Output is correct
16	Correct	248 ms	9400 KB	Output is correct
17	Correct	245 ms	10416 KB	Output is correct
18	Correct	235 ms	10468 KB	Output is correct
19	Correct	201 ms	10512 KB	Output is correct
20	Correct	201 ms	10544 KB	Output is correct
21	Correct	267 ms	11372 KB	Output is correct

Subtask #6
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	4600 KB	Output is correct
2	Correct	33 ms	4520 KB	Output is correct
3	Correct	212 ms	10244 KB	Output is correct
4	Correct	272 ms	10388 KB	Output is correct
5	Correct	278 ms	10516 KB	Output is correct
6	Correct	323 ms	10972 KB	Output is correct
7	Correct	226 ms	10284 KB	Output is correct
8	Correct	229 ms	10344 KB	Output is correct
9	Correct	249 ms	10488 KB	Output is correct
10	Correct	316 ms	11028 KB	Output is correct
11	Correct	301 ms	10992 KB	Output is correct
12	Correct	292 ms	10980 KB	Output is correct
13	Correct	304 ms	9028 KB	Output is correct
14	Correct	276 ms	8856 KB	Output is correct
15	Correct	272 ms	9048 KB	Output is correct
16	Correct	236 ms	8904 KB	Output is correct
17	Correct	304 ms	9108 KB	Output is correct
18	Correct	244 ms	8860 KB	Output is correct
19	Correct	280 ms	10324 KB	Output is correct
20	Correct	296 ms	10532 KB	Output is correct
21	Correct	308 ms	10876 KB	Output is correct
22	Correct	337 ms	10896 KB	Output is correct
23	Correct	336 ms	10876 KB	Output is correct
24	Correct	269 ms	10860 KB	Output is correct
25	Correct	324 ms	10860 KB	Output is correct
26	Correct	290 ms	10868 KB	Output is correct
27	Correct	230 ms	10604 KB	Output is correct
28	Correct	219 ms	10536 KB	Output is correct
29	Correct	237 ms	10732 KB	Output is correct
30	Correct	241 ms	10492 KB	Output is correct
31	Correct	200 ms	10536 KB	Output is correct
32	Correct	233 ms	10452 KB	Output is correct
33	Correct	270 ms	10552 KB	Output is correct
34	Correct	230 ms	10512 KB	Output is correct
35	Correct	200 ms	10436 KB	Output is correct
36	Correct	244 ms	10396 KB	Output is correct
37	Correct	223 ms	10720 KB	Output is correct
38	Correct	231 ms	10472 KB	Output is correct
39	Correct	301 ms	11396 KB	Output is correct
40	Correct	318 ms	11404 KB	Output is correct
41	Correct	375 ms	11420 KB	Output is correct
42	Correct	294 ms	11408 KB	Output is correct

답안 #75237

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