oj.uz

Submission #120280

# Submission time Handle Problem Language Result Execution time Memory
120280 2019-06-24T06:29:53 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
100 / 100
 411 ms 39164 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline void fuk() { puts("ERR!"); exit(-1); }

const int MAXN = 90055;
const int MAXM = 130055;

vector<int> G[MAXN];
int A[MAXM], B[MAXM];

vector<int> TL[MAXN], TR[MAXN];
int TLN, TRN;
int DL[MAXN], DR[MAXN];

int N, M, CA, CB;
int L, EI, TLI, TRI;
int Sidx, Eidx;

map<vector<int>, ll> QMP;
int QCNT;
ll getAns(vector<int> V) {
	vector<int> T(M, 0);
	for(int v : V) T[v] = 1;
	auto it = QMP.find(T);
	if(QMP.end() != it)
		return it->second;
	QCNT++;
	if(60 < QCNT) while(1) puts("WTF");
	ll ret = ask(T);
	QMP[T] = ret;
	return ret;
}

void getOneEdge() {
	int s = 0, e = M-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V;
		for(int i = 0; i <= m; i++) V.eb(i);
		ll t = getAns(V);
		if(t == ll(CA) * L) s = m+1;
		else e = m;
	}
	EI = s;
}

void doBFS(int d[], int sv) {
	fill(d, d+MAXN, INF);
	d[sv] = 0;
	queue<int> PQ; PQ.push(sv);
	for(int idx, dst; !PQ.empty();) {
		idx = PQ.front(); PQ.pop(); dst = d[idx] + 1;
		for(int e : G[idx]) {
			int v = A[e] ^ B[e] ^ idx;
			if(d[v] <= dst) continue;
			d[v] = dst;
			PQ.push(v);
		}
	}
}

void getTL() {
	vector<int> O;
	for(int i = 0; i <= TLN; i++) {
		for(int v : TL[i])
			O.eb(v);
	}
	int n = sz(O), s = 0, e = n-1; for(int m; s < e;) {
		m = (s+e+1) >> 1;
		vector<int> E;
		for(int oi = m; oi < n; oi++) {
			int v = O[oi];
			for(int ed : G[v])
				E.eb(ed);
		}
		ll t = getAns(E);
		if(t == ll(CA) * L) e = m-1;
		else s = m;
	}
	Sidx = O[s];
	TLI = DL[Sidx];
}

int getIdx(vector<int> V) {
	int n = sz(V), s = 0, e = n-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> E;
		for(int i = 0; i <= m; i++) {
			int v = V[i];
			for(int ed : G[v])
				E.eb(ed);
		}
		ll t = getAns(E);
		if(t == ll(CA) * L) s = m+1;
		else e = m;
	}
	return V[s];
}

void process() {
	for(int i = 0; i < M; i++)
		if(A[i] > B[i]) swap(A[i], B[i]);
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	L = getAns(vector<int>()) / CA;
	getOneEdge();

	doBFS(DL, A[EI]);
	doBFS(DR, B[EI]);

	for(int i = 0; i < N; i++) {
		if(DL[i] < DR[i]) {
			TL[DL[i]].eb(i);
			upmax(TLN, DL[i]);
		}
		if(DL[i] > DR[i]) {
			TR[DR[i]].eb(i);
			upmax(TRN, DR[i]);
		}
	}

	getTL();
	TRI = L - TLI - 1;

	Eidx = getIdx(TR[TRI]);

	if(Sidx > Eidx) swap(Sidx, Eidx);
	answer(Sidx, Eidx);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	::N = N;
	::M = sz(U);
	::CA = A;
	::CB = B;
	for(int i = 0; i < M; i++) {
		::A[i] = U[i];
		::B[i] = V[i];
	}
	process();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7392 KB Output is correct
2 Correct 9 ms 7336 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7320 KB Output is correct
5 Correct 8 ms 7320 KB Output is correct
6 Correct 9 ms 7336 KB Output is correct
7 Correct 8 ms 7420 KB Output is correct
8 Correct 8 ms 7288 KB Output is correct
9 Correct 2 ms 7324 KB Output is correct
10 Correct 9 ms 7408 KB Output is correct
11 Correct 9 ms 7288 KB Output is correct
12 Correct 8 ms 7288 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7464 KB Output is correct
2 Correct 22 ms 9436 KB Output is correct
3 Correct 281 ms 27400 KB Output is correct
4 Correct 239 ms 28640 KB Output is correct
5 Correct 227 ms 28000 KB Output is correct
6 Correct 200 ms 24132 KB Output is correct
7 Correct 219 ms 28460 KB Output is correct
8 Correct 217 ms 26920 KB Output is correct
9 Correct 302 ms 28860 KB Output is correct
10 Correct 273 ms 27284 KB Output is correct
11 Correct 228 ms 26272 KB Output is correct
12 Correct 254 ms 26572 KB Output is correct
13 Correct 232 ms 24896 KB Output is correct
14 Correct 279 ms 27572 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9120 KB Output is correct
2 Correct 35 ms 11264 KB Output is correct
3 Correct 98 ms 14120 KB Output is correct
4 Correct 163 ms 27312 KB Output is correct
5 Correct 203 ms 27668 KB Output is correct
6 Correct 208 ms 27004 KB Output is correct
7 Correct 231 ms 28936 KB Output is correct
8 Correct 179 ms 27388 KB Output is correct
9 Correct 306 ms 28528 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 25 ms 9500 KB Output is correct
3 Correct 191 ms 22924 KB Output is correct
4 Correct 257 ms 25172 KB Output is correct
5 Correct 354 ms 28136 KB Output is correct
6 Correct 293 ms 27752 KB Output is correct
7 Correct 269 ms 27408 KB Output is correct
8 Correct 411 ms 27408 KB Output is correct
9 Correct 275 ms 28456 KB Output is correct
10 Correct 244 ms 27980 KB Output is correct
11 Correct 255 ms 24844 KB Output is correct
12 Correct 251 ms 25880 KB Output is correct
13 Correct 290 ms 26704 KB Output is correct
14 Correct 329 ms 27224 KB Output is correct
15 Correct 218 ms 22060 KB Output is correct
16 Correct 222 ms 19888 KB Output is correct
17 Correct 209 ms 25792 KB Output is correct
18 Correct 355 ms 28376 KB Output is correct
19 Correct 270 ms 28116 KB Output is correct
20 Correct 249 ms 25240 KB Output is correct
21 Correct 217 ms 26544 KB Output is correct
22 Correct 268 ms 26488 KB Output is correct
23 Correct 222 ms 31856 KB Output is correct
24 Correct 234 ms 31480 KB Output is correct
25 Correct 281 ms 30876 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9296 KB Output is correct
2 Correct 33 ms 9640 KB Output is correct
3 Correct 274 ms 30800 KB Output is correct
4 Correct 316 ms 29408 KB Output is correct
5 Correct 370 ms 36324 KB Output is correct
6 Correct 385 ms 36088 KB Output is correct
7 Correct 358 ms 35284 KB Output is correct
8 Correct 339 ms 31736 KB Output is correct
9 Correct 268 ms 23500 KB Output is correct
10 Correct 337 ms 31184 KB Output is correct
11 Correct 288 ms 31652 KB Output is correct
12 Correct 325 ms 32132 KB Output is correct
13 Correct 365 ms 33892 KB Output is correct
14 Correct 381 ms 38588 KB Output is correct
15 Correct 320 ms 37188 KB Output is correct
16 Correct 332 ms 36536 KB Output is correct
17 Correct 205 ms 31056 KB Output is correct
18 Correct 219 ms 30848 KB Output is correct
19 Correct 220 ms 29960 KB Output is correct
20 Correct 244 ms 30496 KB Output is correct
21 Correct 399 ms 34668 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9624 KB Output is correct
2 Correct 35 ms 9612 KB Output is correct
3 Correct 240 ms 30716 KB Output is correct
4 Correct 260 ms 32392 KB Output is correct
5 Correct 325 ms 33396 KB Output is correct
6 Correct 300 ms 32256 KB Output is correct
7 Correct 314 ms 29512 KB Output is correct
8 Correct 256 ms 31320 KB Output is correct
9 Correct 343 ms 31656 KB Output is correct
10 Correct 323 ms 35800 KB Output is correct
11 Correct 369 ms 37600 KB Output is correct
12 Correct 377 ms 37576 KB Output is correct
13 Correct 230 ms 27024 KB Output is correct
14 Correct 222 ms 24844 KB Output is correct
15 Correct 247 ms 23852 KB Output is correct
16 Correct 314 ms 31076 KB Output is correct
17 Correct 272 ms 31092 KB Output is correct
18 Correct 271 ms 31456 KB Output is correct
19 Correct 341 ms 32020 KB Output is correct
20 Correct 307 ms 35656 KB Output is correct
21 Correct 357 ms 36052 KB Output is correct
22 Correct 382 ms 39164 KB Output is correct
23 Correct 405 ms 35680 KB Output is correct
24 Correct 348 ms 38600 KB Output is correct
25 Correct 393 ms 34084 KB Output is correct
26 Correct 393 ms 34036 KB Output is correct
27 Correct 252 ms 31656 KB Output is correct
28 Correct 248 ms 30160 KB Output is correct
29 Correct 232 ms 27008 KB Output is correct
30 Correct 268 ms 26868 KB Output is correct
31 Correct 250 ms 29588 KB Output is correct
32 Correct 246 ms 31204 KB Output is correct
33 Correct 224 ms 31200 KB Output is correct
34 Correct 253 ms 31656 KB Output is correct
35 Correct 225 ms 30144 KB Output is correct
36 Correct 243 ms 30644 KB Output is correct
37 Correct 271 ms 31044 KB Output is correct
38 Correct 239 ms 27340 KB Output is correct
39 Correct 319 ms 33644 KB Output is correct
40 Correct 283 ms 33060 KB Output is correct
41 Correct 293 ms 29148 KB Output is correct
42 Correct 369 ms 34208 KB Output is correct