oj.uz

Submission #120274

# Submission time Handle Problem Language Result Execution time Memory
120274 2019-06-24T06:22:59 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
18 / 100
 1500 ms 35724 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> 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 9 ms 7288 KB Output is correct
2 Correct 9 ms 7328 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 9 ms 7388 KB Output is correct
5 Correct 9 ms 7288 KB Output is correct
6 Correct 8 ms 7320 KB Output is correct
7 Correct 8 ms 7320 KB Output is correct
8 Correct 8 ms 7288 KB Output is correct
9 Correct 7 ms 7336 KB Output is correct
10 Correct 7 ms 7336 KB Output is correct
11 Correct 10 ms 7320 KB Output is correct
12 Correct 9 ms 7336 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 32 ms 9356 KB Output is correct
3 Correct 228 ms 28008 KB Output is correct
4 Correct 230 ms 29460 KB Output is correct
5 Correct 231 ms 29232 KB Output is correct
6 Correct 205 ms 24484 KB Output is correct
7 Correct 236 ms 29252 KB Output is correct
8 Correct 171 ms 27624 KB Output is correct
9 Correct 231 ms 26844 KB Output is correct
10 Correct 252 ms 26788 KB Output is correct
11 Correct 282 ms 26244 KB Output is correct
12 Correct 249 ms 27176 KB Output is correct
13 Correct 239 ms 25256 KB Output is correct
14 Correct 365 ms 26928 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9052 KB Output is correct
2 Correct 33 ms 11176 KB Output is correct
3 Correct 72 ms 14600 KB Output is correct
4 Correct 179 ms 30000 KB Output is correct
5 Correct 153 ms 28204 KB Output is correct
6 Correct 195 ms 26928 KB Output is correct
7 Correct 243 ms 28556 KB Output is correct
8 Correct 160 ms 27260 KB Output is correct
9 Correct 251 ms 29248 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7520 KB Output is correct
2 Correct 22 ms 9468 KB Output is correct
3 Correct 153 ms 20596 KB Output is correct
4 Correct 228 ms 25872 KB Output is correct
5 Correct 212 ms 24380 KB Output is correct
6 Correct 241 ms 24776 KB Output is correct
7 Correct 196 ms 23328 KB Output is correct
8 Correct 233 ms 23916 KB Output is correct
9 Correct 268 ms 28896 KB Output is correct
10 Correct 233 ms 29200 KB Output is correct
11 Correct 211 ms 25232 KB Output is correct
12 Correct 215 ms 25612 KB Output is correct
13 Correct 320 ms 27204 KB Output is correct
14 Correct 343 ms 27208 KB Output is correct
15 Correct 209 ms 22340 KB Output is correct
16 Correct 203 ms 20232 KB Output is correct
17 Correct 250 ms 26464 KB Output is correct
18 Correct 324 ms 27324 KB Output is correct
19 Correct 225 ms 23708 KB Output is correct
20 Correct 242 ms 25632 KB Output is correct
21 Correct 224 ms 27432 KB Output is correct
22 Correct 252 ms 27804 KB Output is correct
23 Correct 259 ms 34576 KB Output is correct
24 Execution timed out 3085 ms 35724 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 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 9572 KB Output is correct
2 Correct 49 ms 9520 KB Output is correct
3 Correct 256 ms 30416 KB Output is correct
4 Correct 292 ms 30136 KB Output is correct
5 Correct 292 ms 32328 KB Output is correct
6 Runtime error 298 ms 27192 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -