oj.uz

Submission #120271

# Submission time Handle Problem Language Result Execution time Memory
120271 2019-06-24T06:21:52 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
18 / 100
 1500 ms 32568 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(52 < 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> 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 8 ms 7400 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 9 ms 7288 KB Output is correct
4 Correct 8 ms 7324 KB Output is correct
5 Correct 8 ms 7336 KB Output is correct
6 Correct 8 ms 7324 KB Output is correct
7 Correct 8 ms 7444 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7320 KB Output is correct
10 Correct 8 ms 7320 KB Output is correct
11 Correct 8 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 9 ms 7416 KB Output is correct
2 Correct 31 ms 9304 KB Output is correct
3 Correct 261 ms 27940 KB Output is correct
4 Correct 216 ms 29492 KB Output is correct
5 Correct 263 ms 29208 KB Output is correct
6 Correct 207 ms 24536 KB Output is correct
7 Correct 256 ms 29356 KB Output is correct
8 Correct 220 ms 27692 KB Output is correct
9 Correct 258 ms 26948 KB Output is correct
10 Correct 241 ms 26844 KB Output is correct
11 Correct 243 ms 26348 KB Output is correct
12 Correct 251 ms 27040 KB Output is correct
13 Correct 230 ms 25268 KB Output is correct
14 Correct 281 ms 26936 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9120 KB Output is correct
2 Correct 61 ms 11160 KB Output is correct
3 Correct 75 ms 14688 KB Output is correct
4 Correct 172 ms 30004 KB Output is correct
5 Correct 184 ms 28188 KB Output is correct
6 Correct 212 ms 26924 KB Output is correct
7 Correct 261 ms 28620 KB Output is correct
8 Correct 207 ms 27304 KB Output is correct
9 Correct 264 ms 29300 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7584 KB Output is correct
2 Correct 25 ms 9480 KB Output is correct
3 Correct 187 ms 20432 KB Output is correct
4 Correct 219 ms 25876 KB Output is correct
5 Correct 220 ms 24408 KB Output is correct
6 Correct 238 ms 24768 KB Output is correct
7 Correct 231 ms 23400 KB Output is correct
8 Correct 250 ms 23940 KB Output is correct
9 Correct 242 ms 28932 KB Output is correct
10 Correct 218 ms 29052 KB Output is correct
11 Correct 226 ms 25240 KB Output is correct
12 Correct 247 ms 25600 KB Output is correct
13 Correct 296 ms 27172 KB Output is correct
14 Correct 322 ms 27308 KB Output is correct
15 Correct 194 ms 22348 KB Output is correct
16 Correct 206 ms 20284 KB Output is correct
17 Correct 258 ms 26468 KB Output is correct
18 Correct 333 ms 27344 KB Output is correct
19 Correct 250 ms 23812 KB Output is correct
20 Correct 254 ms 25644 KB Output is correct
21 Correct 252 ms 27368 KB Output is correct
22 Correct 244 ms 27848 KB Output is correct
23 Execution timed out 3096 ms 32568 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 8972 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 31 ms 9572 KB Output is correct
2 Correct 34 ms 9564 KB Output is correct
3 Correct 234 ms 30484 KB Output is correct
4 Correct 316 ms 30184 KB Output is correct
5 Correct 299 ms 32260 KB Output is correct
6 Runtime error 290 ms 27232 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -