oj.uz

Submission #132885

# Submission time Handle Problem Language Result Execution time Memory
132885 2019-07-19T22:23:22 Z KieranHorgan Highway Tolls (IOI18_highway) C++17
5 / 100
 271 ms 9916 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<int> 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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2528 KB Output is correct
3 Correct 4 ms 2440 KB Output is correct
4 Correct 4 ms 2520 KB Output is correct
5 Correct 4 ms 2436 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2436 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2492 KB Output is correct
2 Correct 27 ms 3132 KB Output is correct
3 Correct 246 ms 9128 KB Output is correct
4 Correct 263 ms 9140 KB Output is correct
5 Correct 223 ms 9144 KB Output is correct
6 Correct 252 ms 9084 KB Output is correct
7 Correct 271 ms 9200 KB Output is correct
8 Correct 203 ms 9096 KB Output is correct
9 Correct 252 ms 9300 KB Output is correct
10 Correct 197 ms 9084 KB Output is correct
11 Correct 216 ms 8448 KB Output is correct
12 Correct 184 ms 8452 KB Output is correct
13 Correct 176 ms 8576 KB Output is correct
14 Incorrect 204 ms 8460 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3068 KB Output is correct
2 Correct 42 ms 3696 KB Output is correct
3 Correct 59 ms 4436 KB Output is correct
4 Correct 175 ms 8448 KB Output is correct
5 Correct 163 ms 8348 KB Output is correct
6 Correct 175 ms 8536 KB Output is correct
7 Correct 179 ms 8460 KB Output is correct
8 Correct 190 ms 8464 KB Output is correct
9 Incorrect 183 ms 8344 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 22 ms 3128 KB Output is correct
3 Correct 157 ms 7648 KB Output is correct
4 Correct 182 ms 9068 KB Output is correct
5 Correct 249 ms 8996 KB Output is correct
6 Correct 204 ms 8984 KB Output is correct
7 Correct 224 ms 8980 KB Output is correct
8 Correct 230 ms 9148 KB Output is correct
9 Correct 268 ms 9144 KB Output is correct
10 Correct 251 ms 9140 KB Output is correct
11 Incorrect 210 ms 8456 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3232 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 29 ms 3228 KB Output is correct
2 Correct 22 ms 3288 KB Output is correct
3 Correct 226 ms 9628 KB Output is correct
4 Incorrect 266 ms 9916 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -