oj.uz

Submission #120259

# Submission time Handle Problem Language Result Execution time Memory
120259 2019-06-24T05:59:25 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
36 / 100
 382 ms 36836 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;

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(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]);

	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 7416 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 8 ms 7404 KB Output is correct
4 Correct 8 ms 7288 KB Output is correct
5 Correct 8 ms 7336 KB Output is correct
6 Correct 8 ms 7316 KB Output is correct
7 Correct 8 ms 7316 KB Output is correct
8 Correct 8 ms 7316 KB Output is correct
9 Correct 8 ms 7288 KB Output is correct
10 Correct 8 ms 7336 KB Output is correct
11 Correct 9 ms 7288 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 9 ms 7504 KB Output is correct
2 Correct 40 ms 9220 KB Output is correct
3 Correct 245 ms 27604 KB Output is correct
4 Correct 228 ms 29296 KB Output is correct
5 Correct 233 ms 29020 KB Output is correct
6 Correct 230 ms 24152 KB Output is correct
7 Correct 239 ms 29368 KB Output is correct
8 Correct 248 ms 27272 KB Output is correct
9 Correct 250 ms 26556 KB Output is correct
10 Correct 239 ms 26216 KB Output is correct
11 Correct 317 ms 25416 KB Output is correct
12 Correct 237 ms 26780 KB Output is correct
13 Correct 240 ms 25316 KB Output is correct
14 Correct 299 ms 26260 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9208 KB Output is correct
2 Correct 32 ms 11176 KB Output is correct
3 Correct 81 ms 14572 KB Output is correct
4 Correct 181 ms 30076 KB Output is correct
5 Correct 197 ms 28160 KB Output is correct
6 Correct 196 ms 27008 KB Output is correct
7 Correct 238 ms 28572 KB Output is correct
8 Correct 199 ms 27328 KB Output is correct
9 Correct 230 ms 29276 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7592 KB Output is correct
2 Correct 28 ms 9416 KB Output is correct
3 Correct 180 ms 20056 KB Output is correct
4 Correct 246 ms 25568 KB Output is correct
5 Correct 230 ms 23756 KB Output is correct
6 Correct 213 ms 24100 KB Output is correct
7 Correct 246 ms 23196 KB Output is correct
8 Correct 204 ms 24064 KB Output is correct
9 Correct 261 ms 29052 KB Output is correct
10 Correct 218 ms 28700 KB Output is correct
11 Correct 223 ms 24936 KB Output is correct
12 Correct 241 ms 25140 KB Output is correct
13 Correct 301 ms 26512 KB Output is correct
14 Correct 311 ms 26920 KB Output is correct
15 Correct 219 ms 22072 KB Output is correct
16 Correct 191 ms 19936 KB Output is correct
17 Correct 258 ms 26108 KB Output is correct
18 Correct 328 ms 27316 KB Output is correct
19 Correct 222 ms 23640 KB Output is correct
20 Correct 242 ms 25636 KB Output is correct
21 Correct 220 ms 26884 KB Output is correct
22 Correct 258 ms 27232 KB Output is correct
23 Correct 216 ms 34260 KB Output is correct
24 Incorrect 285 ms 36264 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 33 ms 9332 KB Output is correct
2 Correct 33 ms 9564 KB Output is correct
3 Correct 251 ms 28460 KB Output is correct
4 Correct 285 ms 30212 KB Output is correct
5 Correct 332 ms 36440 KB Output is correct
6 Correct 316 ms 36836 KB Output is correct
7 Correct 331 ms 34392 KB Output is correct
8 Correct 324 ms 31824 KB Output is correct
9 Correct 278 ms 23984 KB Output is correct
10 Correct 274 ms 24624 KB Output is correct
11 Correct 329 ms 32644 KB Output is correct
12 Correct 311 ms 32444 KB Output is correct
13 Correct 314 ms 34116 KB Output is correct
14 Correct 308 ms 33120 KB Output is correct
15 Correct 310 ms 33720 KB Output is correct
16 Correct 293 ms 31452 KB Output is correct
17 Correct 211 ms 31760 KB Output is correct
18 Correct 249 ms 31604 KB Output is correct
19 Correct 262 ms 31904 KB Output is correct
20 Correct 266 ms 32772 KB Output is correct
21 Correct 382 ms 35180 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9536 KB Output is correct
2 Correct 34 ms 9476 KB Output is correct
3 Correct 239 ms 30020 KB Output is correct
4 Correct 280 ms 29296 KB Output is correct
5 Correct 300 ms 31680 KB Output is correct
6 Correct 337 ms 32992 KB Output is correct
7 Correct 265 ms 29232 KB Output is correct
8 Correct 271 ms 29748 KB Output is correct
9 Correct 246 ms 30228 KB Output is correct
10 Correct 309 ms 34128 KB Output is correct
11 Correct 271 ms 33336 KB Output is correct
12 Correct 307 ms 33768 KB Output is correct
13 Correct 291 ms 27036 KB Output is correct
14 Correct 290 ms 24560 KB Output is correct
15 Correct 224 ms 23732 KB Output is correct
16 Correct 263 ms 24716 KB Output is correct
17 Correct 303 ms 32148 KB Output is correct
18 Correct 276 ms 31148 KB Output is correct
19 Correct 304 ms 33024 KB Output is correct
20 Correct 315 ms 32088 KB Output is correct
21 Correct 308 ms 35260 KB Output is correct
22 Correct 314 ms 33688 KB Output is correct
23 Correct 306 ms 36176 KB Output is correct
24 Correct 318 ms 33740 KB Output is correct
25 Correct 322 ms 32608 KB Output is correct
26 Correct 315 ms 33212 KB Output is correct
27 Partially correct 269 ms 33304 KB Output is partially correct
28 Correct 240 ms 31640 KB Output is correct
29 Correct 258 ms 29244 KB Output is correct
30 Correct 182 ms 26860 KB Output is correct
31 Partially correct 233 ms 32208 KB Output is partially correct
32 Correct 245 ms 31520 KB Output is correct
33 Correct 252 ms 31580 KB Output is correct
34 Partially correct 244 ms 32724 KB Output is partially correct
35 Correct 218 ms 31524 KB Output is correct
36 Incorrect 301 ms 32884 KB Output isn't correct
37 Halted 0 ms 0 KB -