oj.uz

Submission #120266

# Submission time Handle Problem Language Result Execution time Memory
120266 2019-06-24T06:13:52 Z 윤교준(#2950) Highway Tolls (IOI18_highway) C++14
51 / 100
 318 ms 32024 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> 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 7404 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 8 ms 7336 KB Output is correct
4 Correct 8 ms 7320 KB Output is correct
5 Correct 9 ms 7324 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 8 ms 7296 KB Output is correct
8 Correct 9 ms 7324 KB Output is correct
9 Correct 9 ms 7336 KB Output is correct
10 Correct 9 ms 7288 KB Output is correct
11 Correct 9 ms 7320 KB Output is correct
12 Correct 8 ms 7288 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7516 KB Output is correct
2 Correct 36 ms 9052 KB Output is correct
3 Correct 202 ms 25948 KB Output is correct
4 Correct 207 ms 28084 KB Output is correct
5 Correct 226 ms 27280 KB Output is correct
6 Correct 193 ms 24464 KB Output is correct
7 Correct 255 ms 27280 KB Output is correct
8 Correct 195 ms 26688 KB Output is correct
9 Correct 230 ms 25228 KB Output is correct
10 Correct 210 ms 24816 KB Output is correct
11 Correct 217 ms 20964 KB Output is correct
12 Correct 204 ms 22104 KB Output is correct
13 Correct 225 ms 21384 KB Output is correct
14 Correct 199 ms 21664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8732 KB Output is correct
2 Correct 32 ms 10424 KB Output is correct
3 Correct 59 ms 12272 KB Output is correct
4 Correct 193 ms 21928 KB Output is correct
5 Correct 152 ms 21920 KB Output is correct
6 Correct 134 ms 21840 KB Output is correct
7 Correct 197 ms 22748 KB Output is correct
8 Correct 189 ms 22268 KB Output is correct
9 Correct 169 ms 22668 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7508 KB Output is correct
2 Correct 31 ms 9336 KB Output is correct
3 Correct 124 ms 18152 KB Output is correct
4 Correct 223 ms 25240 KB Output is correct
5 Correct 233 ms 22416 KB Output is correct
6 Correct 202 ms 22764 KB Output is correct
7 Correct 212 ms 21364 KB Output is correct
8 Correct 213 ms 21992 KB Output is correct
9 Correct 206 ms 26932 KB Output is correct
10 Correct 210 ms 27660 KB Output is correct
11 Correct 225 ms 21404 KB Output is correct
12 Correct 229 ms 21408 KB Output is correct
13 Correct 219 ms 21168 KB Output is correct
14 Correct 212 ms 21340 KB Output is correct
15 Correct 202 ms 22060 KB Output is correct
16 Correct 183 ms 20336 KB Output is correct
17 Correct 243 ms 21916 KB Output is correct
18 Correct 262 ms 22076 KB Output is correct
19 Correct 222 ms 21696 KB Output is correct
20 Correct 172 ms 21048 KB Output is correct
21 Correct 217 ms 26736 KB Output is correct
22 Correct 212 ms 27484 KB Output is correct
23 Correct 247 ms 32024 KB Output is correct
24 Correct 283 ms 31908 KB Output is correct
25 Correct 212 ms 30572 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 9260 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9392 KB Output is correct
2 Correct 43 ms 9332 KB Output is correct
3 Correct 206 ms 28868 KB Output is correct
4 Correct 318 ms 27688 KB Output is correct
5 Correct 261 ms 30224 KB Output is correct
6 Incorrect 311 ms 31220 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -