oj.uz

Submission #120264

# Submission time Handle Problem Language Result Execution time Memory
120264 2019-06-24T06:09:42 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
36 / 100
 366 ms 36832 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;
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;
	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() {
	int s = 0, e = TLN; for(int m; s < e;) {
		m = (s+e+1) >> 1;
		vector<int> V;
		for(int i = m; i <= TLN; i++) {
			for(int v : TL[i]) {
				for(int ed : G[v])
					V.eb(ed);
			}
		}
		ll t = getAns(V);
		if(t == ll(CA) * L) e = m-1;
		else s = m;
	}
	TLI = s;
}

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(abs(DL[i] - DR[i]) > 1) fuk();
		// TODO remove =
		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;

	Sidx = getIdx(TL[TLI]);
	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 9 ms 7288 KB Output is correct
2 Correct 9 ms 7336 KB Output is correct
3 Correct 9 ms 7288 KB Output is correct
4 Correct 8 ms 7336 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7336 KB Output is correct
7 Correct 9 ms 7288 KB Output is correct
8 Correct 13 ms 7288 KB Output is correct
9 Correct 10 ms 7336 KB Output is correct
10 Correct 10 ms 7320 KB Output is correct
11 Correct 10 ms 7320 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 32 ms 9248 KB Output is correct
3 Correct 242 ms 27600 KB Output is correct
4 Correct 244 ms 29360 KB Output is correct
5 Correct 236 ms 29084 KB Output is correct
6 Correct 229 ms 24148 KB Output is correct
7 Correct 274 ms 29396 KB Output is correct
8 Correct 215 ms 27312 KB Output is correct
9 Correct 241 ms 26656 KB Output is correct
10 Correct 267 ms 26260 KB Output is correct
11 Correct 281 ms 25520 KB Output is correct
12 Correct 251 ms 26768 KB Output is correct
13 Correct 230 ms 25224 KB Output is correct
14 Correct 330 ms 26160 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9116 KB Output is correct
2 Correct 48 ms 11236 KB Output is correct
3 Correct 85 ms 14544 KB Output is correct
4 Correct 214 ms 29992 KB Output is correct
5 Correct 209 ms 28132 KB Output is correct
6 Correct 167 ms 27036 KB Output is correct
7 Correct 235 ms 28556 KB Output is correct
8 Correct 190 ms 27364 KB Output is correct
9 Correct 236 ms 29248 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7504 KB Output is correct
2 Correct 27 ms 9432 KB Output is correct
3 Correct 176 ms 20172 KB Output is correct
4 Correct 207 ms 25652 KB Output is correct
5 Correct 241 ms 23852 KB Output is correct
6 Correct 202 ms 24088 KB Output is correct
7 Correct 249 ms 23256 KB Output is correct
8 Correct 230 ms 24180 KB Output is correct
9 Correct 259 ms 29080 KB Output is correct
10 Correct 203 ms 28696 KB Output is correct
11 Correct 223 ms 24844 KB Output is correct
12 Correct 228 ms 25204 KB Output is correct
13 Correct 287 ms 26536 KB Output is correct
14 Correct 288 ms 26920 KB Output is correct
15 Correct 228 ms 21976 KB Output is correct
16 Correct 198 ms 19964 KB Output is correct
17 Correct 246 ms 26120 KB Output is correct
18 Correct 324 ms 27392 KB Output is correct
19 Correct 162 ms 23624 KB Output is correct
20 Correct 232 ms 25552 KB Output is correct
21 Correct 218 ms 26920 KB Output is correct
22 Correct 252 ms 27176 KB Output is correct
23 Correct 278 ms 34228 KB Output is correct
24 Incorrect 301 ms 36272 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9392 KB Output is correct
2 Correct 33 ms 9572 KB Output is correct
3 Correct 270 ms 28816 KB Output is correct
4 Correct 284 ms 30208 KB Output is correct
5 Correct 335 ms 36400 KB Output is correct
6 Correct 332 ms 36832 KB Output is correct
7 Correct 321 ms 35752 KB Output is correct
8 Correct 291 ms 32872 KB Output is correct
9 Correct 267 ms 23996 KB Output is correct
10 Correct 268 ms 24568 KB Output is correct
11 Correct 331 ms 32680 KB Output is correct
12 Correct 316 ms 32444 KB Output is correct
13 Correct 275 ms 34096 KB Output is correct
14 Correct 310 ms 34248 KB Output is correct
15 Correct 312 ms 34260 KB Output is correct
16 Correct 339 ms 33436 KB Output is correct
17 Correct 235 ms 31748 KB Output is correct
18 Correct 258 ms 31612 KB Output is correct
19 Correct 259 ms 31912 KB Output is correct
20 Correct 260 ms 32848 KB Output is correct
21 Correct 366 ms 35176 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9536 KB Output is correct
2 Correct 34 ms 9524 KB Output is correct
3 Correct 256 ms 30244 KB Output is correct
4 Correct 275 ms 29740 KB Output is correct
5 Correct 277 ms 32368 KB Output is correct
6 Correct 355 ms 34400 KB Output is correct
7 Correct 228 ms 29296 KB Output is correct
8 Correct 235 ms 29744 KB Output is correct
9 Correct 284 ms 30816 KB Output is correct
10 Correct 276 ms 35344 KB Output is correct
11 Correct 347 ms 33900 KB Output is correct
12 Correct 304 ms 34336 KB Output is correct
13 Correct 283 ms 27084 KB Output is correct
14 Correct 269 ms 24576 KB Output is correct
15 Correct 252 ms 23828 KB Output is correct
16 Correct 307 ms 24684 KB Output is correct
17 Correct 337 ms 32156 KB Output is correct
18 Correct 273 ms 31148 KB Output is correct
19 Correct 328 ms 32996 KB Output is correct
20 Correct 291 ms 31976 KB Output is correct
21 Correct 327 ms 34652 KB Output is correct
22 Correct 342 ms 33084 KB Output is correct
23 Correct 352 ms 36820 KB Output is correct
24 Correct 361 ms 34140 KB Output is correct
25 Correct 336 ms 33620 KB Output is correct
26 Correct 354 ms 33216 KB Output is correct
27 Partially correct 250 ms 33296 KB Output is partially correct
28 Correct 204 ms 31604 KB Output is correct
29 Correct 263 ms 29268 KB Output is correct
30 Correct 243 ms 26868 KB Output is correct
31 Partially correct 245 ms 32300 KB Output is partially correct
32 Correct 241 ms 31536 KB Output is correct
33 Correct 226 ms 31560 KB Output is correct
34 Partially correct 249 ms 32720 KB Output is partially correct
35 Correct 255 ms 31516 KB Output is correct
36 Incorrect 271 ms 32932 KB Output isn't correct
37 Halted 0 ms 0 KB -