oj.uz

Submission #120265

# Submission time Handle Problem Language Result Execution time Memory
120265 2019-06-24T06:11:01 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
18 / 100
 318 ms 36612 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();

	if(getAns(vector<int>(1, EI)) != ll(CA) * (L-1) + CB) fuk();

	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 7292 KB Output is correct
2 Correct 9 ms 7284 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 8 ms 7324 KB Output is correct
5 Correct 8 ms 7324 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 8 ms 7288 KB Output is correct
8 Correct 8 ms 7404 KB Output is correct
9 Correct 8 ms 7388 KB Output is correct
10 Correct 9 ms 7336 KB Output is correct
11 Correct 9 ms 7288 KB Output is correct
12 Correct 8 ms 7336 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 34 ms 9404 KB Output is correct
3 Correct 254 ms 27976 KB Output is correct
4 Correct 242 ms 29652 KB Output is correct
5 Correct 248 ms 29456 KB Output is correct
6 Correct 233 ms 24524 KB Output is correct
7 Correct 241 ms 29712 KB Output is correct
8 Correct 224 ms 27632 KB Output is correct
9 Correct 244 ms 26984 KB Output is correct
10 Correct 228 ms 26592 KB Output is correct
11 Correct 285 ms 25768 KB Output is correct
12 Correct 224 ms 27128 KB Output is correct
13 Correct 237 ms 25588 KB Output is correct
14 Correct 304 ms 26264 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9148 KB Output is correct
2 Correct 43 ms 11240 KB Output is correct
3 Correct 68 ms 14704 KB Output is correct
4 Correct 166 ms 30404 KB Output is correct
5 Correct 163 ms 28580 KB Output is correct
6 Correct 196 ms 27288 KB Output is correct
7 Correct 242 ms 28896 KB Output is correct
8 Correct 177 ms 27632 KB Output is correct
9 Correct 201 ms 29612 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 23 ms 9428 KB Output is correct
3 Correct 221 ms 20332 KB Output is correct
4 Correct 181 ms 25884 KB Output is correct
5 Correct 211 ms 24116 KB Output is correct
6 Correct 179 ms 24492 KB Output is correct
7 Correct 243 ms 23540 KB Output is correct
8 Correct 262 ms 24412 KB Output is correct
9 Correct 219 ms 29456 KB Output is correct
10 Correct 224 ms 29092 KB Output is correct
11 Correct 224 ms 25192 KB Output is correct
12 Correct 234 ms 25484 KB Output is correct
13 Correct 291 ms 26904 KB Output is correct
14 Correct 299 ms 27248 KB Output is correct
15 Correct 224 ms 22400 KB Output is correct
16 Correct 220 ms 19884 KB Output is correct
17 Correct 241 ms 26496 KB Output is correct
18 Correct 299 ms 27284 KB Output is correct
19 Correct 228 ms 23992 KB Output is correct
20 Correct 286 ms 26000 KB Output is correct
21 Correct 217 ms 27228 KB Output is correct
22 Correct 218 ms 27784 KB Output is correct
23 Correct 267 ms 34564 KB Output is correct
24 Incorrect 318 ms 36612 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9388 KB Output is correct
2 Correct 34 ms 9620 KB Output is correct
3 Correct 184 ms 29244 KB Output is correct
4 Correct 283 ms 30716 KB Output is correct
5 Runtime error 275 ms 24032 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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