oj.uz

Submission #120268

# Submission time Handle Problem Language Result Execution time Memory
120268 2019-06-24T06:17:18 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
18 / 100
 314 ms 36668 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() {
	{
		vector<int> V;
		for(int i = 0; i <= TLN; i++) {
			for(int v : TL[i])
				for(int ed : G[v])
					V.eb(ed);
		}
		ll t = getAns(V);
		TLI = (t - ll(CA) * L) / (CB-CA) - 1;
	}

	int s = 0, e = TLN; for(int m; s < e;) {
		m = (s+e+1) >> 1;
		vector<int> E;
		for(int i = m; i <= TLN; i++) {
			for(int v : TL[i]) {
				for(int ed : G[v])
					E.eb(ed);
			}
		}
		ll t = getAns(E);
		if(t == ll(CA) * L) e = m-1;
		else s = m;
	}
	if(TLI != s) fuk();
	/*
	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(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 10 ms 7320 KB Output is correct
2 Correct 8 ms 7324 KB Output is correct
3 Correct 8 ms 7336 KB Output is correct
4 Correct 9 ms 7372 KB Output is correct
5 Correct 8 ms 7324 KB Output is correct
6 Correct 8 ms 7320 KB Output is correct
7 Correct 9 ms 7336 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7336 KB Output is correct
10 Correct 9 ms 7336 KB Output is correct
11 Correct 9 ms 7288 KB Output is correct
12 Correct 9 ms 7288 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7444 KB Output is correct
2 Correct 34 ms 9352 KB Output is correct
3 Correct 251 ms 27952 KB Output is correct
4 Correct 233 ms 29400 KB Output is correct
5 Correct 251 ms 29196 KB Output is correct
6 Correct 240 ms 24540 KB Output is correct
7 Correct 248 ms 29324 KB Output is correct
8 Correct 222 ms 27664 KB Output is correct
9 Correct 240 ms 26940 KB Output is correct
10 Correct 238 ms 26768 KB Output is correct
11 Correct 280 ms 26312 KB Output is correct
12 Correct 246 ms 27032 KB Output is correct
13 Correct 245 ms 25240 KB Output is correct
14 Correct 314 ms 27032 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9080 KB Output is correct
2 Correct 46 ms 11156 KB Output is correct
3 Correct 91 ms 14616 KB Output is correct
4 Correct 201 ms 30012 KB Output is correct
5 Correct 191 ms 28164 KB Output is correct
6 Correct 200 ms 26924 KB Output is correct
7 Correct 282 ms 28580 KB Output is correct
8 Correct 167 ms 27392 KB Output is correct
9 Correct 224 ms 29256 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7464 KB Output is correct
2 Correct 32 ms 9564 KB Output is correct
3 Correct 172 ms 20448 KB Output is correct
4 Correct 212 ms 25912 KB Output is correct
5 Correct 219 ms 24352 KB Output is correct
6 Correct 254 ms 24700 KB Output is correct
7 Correct 236 ms 23284 KB Output is correct
8 Correct 239 ms 23904 KB Output is correct
9 Correct 260 ms 28940 KB Output is correct
10 Correct 294 ms 29048 KB Output is correct
11 Correct 238 ms 25200 KB Output is correct
12 Correct 213 ms 25620 KB Output is correct
13 Correct 290 ms 27216 KB Output is correct
14 Correct 291 ms 27212 KB Output is correct
15 Correct 208 ms 22352 KB Output is correct
16 Correct 229 ms 20216 KB Output is correct
17 Correct 234 ms 26528 KB Output is correct
18 Correct 301 ms 27280 KB Output is correct
19 Correct 246 ms 23752 KB Output is correct
20 Correct 238 ms 25620 KB Output is correct
21 Correct 255 ms 27424 KB Output is correct
22 Correct 251 ms 27832 KB Output is correct
23 Correct 245 ms 34568 KB Output is correct
24 Incorrect 286 ms 36668 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 8964 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9528 KB Output is correct
2 Correct 35 ms 9504 KB Output is correct
3 Correct 259 ms 30476 KB Output is correct
4 Correct 310 ms 30192 KB Output is correct
5 Correct 291 ms 32332 KB Output is correct
6 Runtime error 310 ms 27296 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -