oj.uz

답안 #132886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132886 2019-07-19T22:24:13 Z KieranHorgan 통행료 (IOI18_highway) C++17
18 / 100
 392 ms 12876 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, M, A, B;
vector<signed> U, V;

const int MAXN = 90000;
const int MAXM = 130000;

int queriesSoFar = 0;

long long allLightCost;

vector<pair<int,int>> AdjList[90005];
bitset<MAXN> nodesToCheck;
vector<signed> edgesToCheck;

long long checkNodes() {
	edgesToCheck.assign(M,0);
	for(int v = 0; v < N; v++) {
		if(!nodesToCheck[v])
			continue;
		for(auto p: AdjList[v])
			edgesToCheck[p.second]=1;
	}

	queriesSoFar++;
	return ask(edgesToCheck);
}

void find_pair(signed N_, vector<signed> U_, vector<signed> V_, signed A_, signed B_) {
	N=N_; U=U_;V=V_;A=A_;B=B_;
	M = U.size();

	edgesToCheck.assign(M, 0);

	srand(time(NULL));

	for(int e = 0; e < M; e++) {
		AdjList[U[e]].push_back({V[e],e});
		AdjList[V[e]].push_back({U[e],e});
	}

	allLightCost = checkNodes();

	//-----------Get Edge In Path-------------//
	vector<int> randomisedNodes(N);
	for(int i = 0; i < N; i++)
		randomisedNodes[i]=i;
	random_shuffle(randomisedNodes.begin(), randomisedNodes.end());

	int lo = 0;
	int hi = N;
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < mid; i++)
			nodesToCheck[randomisedNodes[i]]=1;
		long long cur = checkNodes();
		if(cur > allLightCost) hi = mid;
		else lo = mid;
	}
	int onPath = randomisedNodes[lo];
	//-----------Get Edge In Path-------------//


	//------------Get Nearer End--------------//
	vector<int> dist(N,N+10);
	dist[onPath] = 0;
	queue<pair<int,int>> q;
	q.push({onPath, 0});
	while(!q.empty()) {
		int u = q.front().first;
		int d = q.front().second;
		q.pop();

		for(auto p: AdjList[u]) {
			int v = p.first;
			if(dist[v] > d+1) {
				dist[v] = d+1;
				q.push({v,d+1});
			}
		}
	}

	int diff = allLightCost/A;
	lo = 0;
	hi = (diff/2)+1;
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < N; i++)
			if(dist[i] < mid)
				nodesToCheck[i] = 1;
		long long expected = allLightCost - (mid)*2*A + (mid)*2*B;
		long long act = checkNodes();
		if(expected == act) lo = mid;
		else hi = mid;
	}
	int distToNearest = lo;
	//------------Get Nearer End--------------//


	//------------Get Closer Node-------------//
	vector<int> possibilites;
	for(int i = 0; i < N; i++)
		if(dist[i] == distToNearest)
			possibilites.push_back(i);
	random_shuffle(possibilites.begin(), possibilites.end());
	lo = 0;
	hi = possibilites.size();
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < mid; i++)
			nodesToCheck[possibilites[i]]=1;
		long long cur = checkNodes();
		if(cur == allLightCost)
			lo = mid;
		else if(cur == allLightCost + (B-A) + (B-A) + (B-A))
			hi = mid;
		else if(cur == allLightCost + (B-A))
			hi = mid;
		else {
			if(distToNearest*2 == diff)
				hi = mid;
			else
				lo = mid;
		}
	}
	int S = possibilites[lo];
	//------------Get Closer Node-------------//


	//------------Get Further Node------------//
	possibilites.clear();
	int distToFurther = diff - distToNearest;
	for(int i = 0; i < N; i++)
		if(dist[i] == distToFurther && i != S)
			possibilites.push_back(i);
	random_shuffle(possibilites.begin(), possibilites.end());
	lo = 0;
	hi = possibilites.size();
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < mid; i++) 
			nodesToCheck[possibilites[i]]=1;
		long long cur = checkNodes();
		if(cur == allLightCost)
			lo = mid;
		else
			hi = mid;
	}
	int T = possibilites[lo];
	//------------Get Further Node------------//
	answer(S,T);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2440 KB Output is correct
2 Correct 4 ms 2444 KB Output is correct
3 Correct 4 ms 2440 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2440 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2436 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 2 ms 2528 KB Output is correct
12 Correct 4 ms 2428 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2428 KB Output is correct
2 Correct 25 ms 3308 KB Output is correct
3 Correct 242 ms 11248 KB Output is correct
4 Correct 234 ms 11224 KB Output is correct
5 Correct 271 ms 11308 KB Output is correct
6 Correct 218 ms 11116 KB Output is correct
7 Correct 269 ms 11168 KB Output is correct
8 Correct 254 ms 11192 KB Output is correct
9 Correct 229 ms 11316 KB Output is correct
10 Correct 248 ms 11228 KB Output is correct
11 Correct 215 ms 11012 KB Output is correct
12 Correct 247 ms 11020 KB Output is correct
13 Correct 218 ms 11140 KB Output is correct
14 Correct 289 ms 11132 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3344 KB Output is correct
2 Correct 43 ms 4264 KB Output is correct
3 Correct 55 ms 5060 KB Output is correct
4 Correct 182 ms 10668 KB Output is correct
5 Correct 186 ms 10476 KB Output is correct
6 Correct 164 ms 10556 KB Output is correct
7 Correct 201 ms 10468 KB Output is correct
8 Correct 145 ms 10564 KB Output is correct
9 Correct 195 ms 10476 KB Output is correct

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 18 ms 3304 KB Output is correct
3 Correct 162 ms 9180 KB Output is correct
4 Correct 230 ms 11100 KB Output is correct
5 Correct 206 ms 11104 KB Output is correct
6 Correct 219 ms 11004 KB Output is correct
7 Correct 235 ms 11232 KB Output is correct
8 Correct 230 ms 11188 KB Output is correct
9 Correct 214 ms 11148 KB Output is correct
10 Correct 221 ms 11252 KB Output is correct
11 Correct 302 ms 11028 KB Output is correct
12 Correct 265 ms 11028 KB Output is correct
13 Correct 215 ms 11016 KB Output is correct
14 Correct 266 ms 11016 KB Output is correct
15 Correct 215 ms 11144 KB Output is correct
16 Correct 257 ms 11112 KB Output is correct
17 Correct 278 ms 11068 KB Output is correct
18 Correct 272 ms 11024 KB Output is correct
19 Correct 246 ms 11036 KB Output is correct
20 Correct 230 ms 11020 KB Output is correct
21 Correct 330 ms 12844 KB Output is correct
22 Correct 372 ms 12876 KB Output is correct
23 Correct 311 ms 11772 KB Output is correct
24 Incorrect 392 ms 11612 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3516 KB Output is correct
2 Incorrect 24 ms 3592 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 3500 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -