oj.uz

Submission #132884

# Submission time Handle Problem Language Result Execution time Memory
132884 2019-07-19T22:21:49 Z KieranHorgan Highway Tolls (IOI18_highway) C++17
5 / 100
 272 ms 9164 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;

int 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 2440 KB Output is correct
2 Correct 4 ms 2440 KB Output is correct
3 Correct 4 ms 2440 KB Output is correct
4 Correct 4 ms 2440 KB Output is correct
5 Correct 4 ms 2516 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2520 KB Output is correct
8 Correct 4 ms 2436 KB Output is correct
9 Correct 4 ms 2440 KB Output is correct
10 Correct 4 ms 2428 KB Output is correct
11 Correct 4 ms 2436 KB Output is correct
12 Correct 4 ms 2440 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 3064 KB Output is correct
3 Correct 257 ms 9140 KB Output is correct
4 Correct 239 ms 9132 KB Output is correct
5 Correct 248 ms 9128 KB Output is correct
6 Correct 224 ms 9084 KB Output is correct
7 Correct 243 ms 9132 KB Output is correct
8 Correct 258 ms 9124 KB Output is correct
9 Correct 258 ms 9164 KB Output is correct
10 Correct 272 ms 9092 KB Output is correct
11 Correct 215 ms 8468 KB Output is correct
12 Correct 232 ms 8444 KB Output is correct
13 Correct 194 ms 8456 KB Output is correct
14 Incorrect 193 ms 8344 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3068 KB Output is correct
2 Correct 44 ms 3780 KB Output is correct
3 Correct 60 ms 4320 KB Output is correct
4 Correct 169 ms 8444 KB Output is correct
5 Correct 141 ms 8340 KB Output is correct
6 Correct 165 ms 8456 KB Output is correct
7 Correct 164 ms 8452 KB Output is correct
8 Correct 180 ms 8444 KB Output is correct
9 Incorrect 126 ms 8424 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2512 KB Output is correct
2 Correct 27 ms 3064 KB Output is correct
3 Correct 139 ms 7648 KB Output is correct
4 Correct 212 ms 9072 KB Output is correct
5 Correct 236 ms 9164 KB Output is correct
6 Correct 203 ms 9072 KB Output is correct
7 Correct 189 ms 9040 KB Output is correct
8 Correct 240 ms 9020 KB Output is correct
9 Incorrect 172 ms 9024 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 3164 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 28 ms 3228 KB Output is correct
2 Incorrect 29 ms 3220 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -