Submission #784215

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784215	2023-07-15T21:17:00 Z	APROHACK	Highway Tolls (IOI18_highway)	C++14	18 / 100	110 ms	13304 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
int m, n;
vector<int>adj[100000];
vector<int>idx[100000];
vector<int>options;
vector<int>edjes;
bool vis[100000];
ll largo;
void bfs(int s){
	memset(vis, false, sizeof vis);
	int distancia[100000];
	queue<int>cola;
	distancia[0] = 0;
	vis[0] = true;
	cola.push(s);
	while(!cola.empty()){
		int cur = cola.front();
		//cout << cur << endl;
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(vis[adj[cur][i]])continue;
			vis[adj[cur][i]] = true;
			distancia[adj[cur][i]] = distancia[cur] + 1;
			if(distancia[adj[cur][i]] == largo){
				options.pb(adj[cur][i]);
				edjes.pb(idx[cur][i]);
			}
			cola.push(adj[cur][i]);
		}
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	n = N;
	bool val = true;
	for(int i = 0 ; i < m ; i ++){
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
		idx[U[i]].pb(i);
		idx[V[i]].pb(i);
		if(U[i] != i)val = false;
		if(V[i] != i + 1)val = false;
	}
	vector<int>w;
	for(int i = 0 ; i < m ; i ++)w.pb(0);
	ll ans = ask(w);
	largo = ans / A;
	if(val){
		int ansA, ansB;
		int li = 0, ls = m-1, pos;
		pos = (li + ls )/2;
		while(li+1 < ls){
			for(int i = 0 ; i < m ; i ++)w[i] = 0;
			for(int i = pos ; i <= ls ; i ++){
				w[i] = 1;
			}
			if(ask(w) > largo*A){
				li = pos;
			}else{
				ls = pos -1;
			}
			pos = (li + ls)/2;
		}
		for(int i = 0 ; i < m ; i ++)w[i] = 0;
		w[ls] = 1;
		if(ask(w) > largo*A){
			ansA = V[ls];
		}else ansA = V[li];
		
		
		li = 0, ls = m-1, pos;
		pos = (li + ls )/2;
		while(li+1 < ls){
			for(int i = 0 ; i < m ; i ++)w[i] = 0;
			for(int i = li ; i <= pos ; i ++){
				w[i] = 1;
			}
			if(ask(w) > largo*A){
				ls = pos;
			}else{
				li = pos +1;
			}
			pos = (li + ls)/2;
		}
		for(int i = 0 ; i < m ; i ++)w[i] = 0;
		w[li] = 1;
		if(ask(w) > largo*A){
			ansB = U[li];
		}else ansB = U[ls];
		answer(ansA, ansB);
	}else{

		bfs(0);
		int li = 0, ls = options.size()-1;
		int pos = (li + ls)/2;
		while(li + 1 < ls){
			for(int i = 0 ; i < m ; i ++)w[i] = 0;
			for(int i = pos ; i <= ls ; i ++)w[edjes[i]] = 1;
			if(ask(w) > largo*A){
				li = pos;
			}else{
				ls = pos -1;
			}
			pos = (li + ls )/2;
		}
		for(int i = 0 ;  i < m ; i ++)w[i] = 0;
		w[edjes[li]] = 1;
		if(ask(w) > largo*A)answer(0, options[li]);
		else answer(0, options[ls]);
	}
}

Compilation message

highway.cpp: In function 'void bfs(int)':
highway.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i = 0 ; i < adj[cur].size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:78:24: warning: right operand of comma operator has no effect [-Wunused-value]
   78 |   li = 0, ls = m-1, pos;
      |                        ^

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5456 KB	Output is correct
2	Correct	2 ms	5456 KB	Output is correct
3	Correct	2 ms	5456 KB	Output is correct
4	Correct	2 ms	5456 KB	Output is correct
5	Correct	3 ms	5456 KB	Output is correct
6	Correct	2 ms	5456 KB	Output is correct
7	Correct	2 ms	5400 KB	Output is correct
8	Correct	2 ms	5456 KB	Output is correct
9	Correct	2 ms	5456 KB	Output is correct
10	Correct	2 ms	5456 KB	Output is correct
11	Correct	4 ms	5456 KB	Output is correct
12	Correct	2 ms	5456 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5456 KB	Output is correct
2	Correct	9 ms	6400 KB	Output is correct
3	Correct	102 ms	13240 KB	Output is correct
4	Correct	84 ms	13240 KB	Output is correct
5	Correct	79 ms	13300 KB	Output is correct
6	Correct	88 ms	13116 KB	Output is correct
7	Correct	90 ms	13208 KB	Output is correct
8	Correct	109 ms	13304 KB	Output is correct
9	Correct	99 ms	13112 KB	Output is correct
10	Correct	75 ms	13252 KB	Output is correct
11	Correct	110 ms	12996 KB	Output is correct
12	Correct	100 ms	12996 KB	Output is correct
13	Correct	108 ms	12932 KB	Output is correct
14	Correct	100 ms	12996 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	5848 KB	Output is correct
2	Correct	26 ms	6676 KB	Output is correct
3	Correct	22 ms	7452 KB	Output is correct
4	Correct	109 ms	12604 KB	Output is correct
5	Correct	85 ms	12676 KB	Output is correct
6	Correct	105 ms	12624 KB	Output is correct
7	Correct	87 ms	12612 KB	Output is correct
8	Correct	72 ms	12608 KB	Output is correct
9	Correct	99 ms	12620 KB	Output is correct