oj.uz

Submission #787108

# Submission time Handle Problem Language Result Execution time Memory
787108 2023-07-18T20:24:49 Z APROHACK Highway Tolls (IOI18_highway) C++17
11 / 100
 133 ms 14988 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
ll m, n, a, b, largo;
vector<int>adj[100000];
vector<int>idx[100000];


void llenar(int dd, int ht, int v, vector<int>&w){
	for(int i = dd ; i <= ht ; i ++)w[i] = v;
}

void find_edje(int &ejeMedio, vector<int>&w){
	int li = 0, ls = m-1, pos;
	pos = (li + ls)/2;
	int tried[130000];
	for(int i = 0 ; i < m ; i ++)tried[i] = -1;
	while(li + 1 < ls){
		llenar(0, m-1, 0, w);
		llenar(0, pos, 1, w);
		ll res = ask(w);
		tried[pos] = res;
		if(res > largo*a){
			ls = pos;
		}else{
			li = pos + 1;
		}
		pos = (li + ls ) / 2 ;
	}
	if(tried[li] == -1){
		llenar(0, m-1, 0, w);
		llenar(0, pos, 1, w);
		tried[li] = ask(w);
	}
	if(tried[li] > largo*a){
		ejeMedio = li;
	}else ejeMedio = ls;
}

vector<int>getEdjes(int dd, int banned, vector<int>&dist, vector<int>&nodes){
	queue<int>cola;
	dist.clear();
	nodes.clear();
	vector<int>ans;
	for(int i = 0 ; i < n ; i ++)dist.pb(INT_MAX);
	cola.push(dd);
	dist[dd] = 0;
	bool vis[n+1];
	memset(vis, false, sizeof vis);
	vis[dd] = true;
	while(!cola.empty()){
		int cur = cola.front();
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(idx[cur][i] == banned)continue;
			if(vis[adj[cur][i]])continue;
			vis[adj[cur][i]] = true;
			dist[adj[cur][i]] = dist[cur] + 1;
			cola.push(adj[cur][i]);
			ans.pb(idx[cur][i]);
			nodes.pb(adj[cur][i]);
		}
	}
	
	return ans;
}

int cualAfecta(vector<int>&nodos, vector<int>&ejes, vector<int>&w){
	int li = 0, ls = ejes.size()-1;
	int pos = (li + ls)/2;
	while(li + 1 < ls){
		llenar(0, m-1, 0, w);
		for(int i = li ; i <= pos ; i ++)w[ejes[i]] = 1;
		if(ask(w) > largo*a){
			ls = pos;
		}else{
			li = pos + 1;
		}
		pos = (li + ls)/2;
	}
	if(li == ls)return nodos[li];
	llenar(0, m-1, 0, w);
	w[ejes[li]] = 1;
	if(ask(w) > largo * a)return nodos[li];
	else return nodos[ls];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	a = A;
	b = B;
	vector<int>w;
	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);
		w.pb(0);
	}
	largo = ask(w)/a;
	int ejeMedio;
	find_edje(ejeMedio, w);
	//cout << ejeMedio << endl;
	//cout << U[ejeMedio] << " " << V[ejeMedio] << endl;
	
	
	vector<int>distancias, nodos, ejes;
	ejes = getEdjes(V[ejeMedio], ejeMedio, distancias, nodos);
	llenar(0, m-1, 0, w);
	for(auto i : ejes)w[i] = 1;
	ll distkt = (ask(w)-largo*a)/(b-a);
	//cout << "dist " << V[ejeMedio] << " = " << distkt << endl;
	int s, t;
	if(distkt == 0){
		t = V[ejeMedio];
	}else{
		vector<int>tempNodos, tempEje;
		for(int i = 0 ; i < nodos.size() ; i ++){
			if(distancias[nodos[i]] == distkt){
				tempNodos.pb(nodos[i]);
				tempEje.pb(ejes[i]);
			}
		}
		//cout << " opciones " ;
		//for(auto i : tempNodos)cout << i << " " ;
		//cout << endl;
		
		t = cualAfecta(tempNodos, tempEje, w);
	}
	ejes = getEdjes(U[ejeMedio], ejeMedio, distancias, nodos);
	llenar(0, m-1, 0, w);
	for(auto i : ejes)w[i] = 1;
	distkt = (ask(w)-largo*a)/(b-a);
	//cout << "dist " << U[ejeMedio] << " = " << distkt << endl;
	
	if(distkt == 0){
		s = U[ejeMedio];
	}else{
		vector<int>tempNodos, tempEje;
		for(int i = 0 ; i < nodos.size() ; i ++){
			if(distancias[nodos[i]] == distkt){
				tempNodos.pb(nodos[i]);
				tempEje.pb(ejes[i]);
			}
		}
		
		s = cualAfecta(tempNodos, tempEje, w);
	}
	
	//cout << s << " " << t << endl;
	answer(s, t);
	

}

Compilation message

highway.cpp: In function 'std::vector<int> getEdjes(int, int, std::vector<int>&, std::vector<int>&)':
highway.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   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:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i = 0 ; i < nodos.size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~
highway.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for(int i = 0 ; i < nodos.size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5456 KB Output is correct
2 Correct 4 ms 5608 KB Output is correct
3 Correct 3 ms 5396 KB Output is correct
4 Correct 3 ms 5392 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 5512 KB Output is correct
8 Correct 3 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 3 ms 5456 KB Output is correct
12 Correct 4 ms 5456 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 12 ms 6464 KB Output is correct
3 Correct 116 ms 14760 KB Output is correct
4 Correct 84 ms 14760 KB Output is correct
5 Correct 84 ms 14592 KB Output is correct
6 Correct 100 ms 14772 KB Output is correct
7 Correct 80 ms 14524 KB Output is correct
8 Correct 98 ms 14764 KB Output is correct
9 Correct 95 ms 14736 KB Output is correct
10 Correct 95 ms 14772 KB Output is correct
11 Correct 91 ms 14108 KB Output is correct
12 Correct 94 ms 14740 KB Output is correct
13 Correct 106 ms 14380 KB Output is correct
14 Incorrect 97 ms 14388 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6448 KB Output is correct
2 Correct 15 ms 7416 KB Output is correct
3 Correct 22 ms 8368 KB Output is correct
4 Correct 91 ms 14176 KB Output is correct
5 Correct 61 ms 14136 KB Output is correct
6 Correct 108 ms 14324 KB Output is correct
7 Correct 64 ms 14288 KB Output is correct
8 Correct 60 ms 14064 KB Output is correct
9 Correct 108 ms 14988 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5596 KB Output is correct
2 Correct 14 ms 6480 KB Output is correct
3 Correct 91 ms 12700 KB Output is correct
4 Correct 112 ms 14768 KB Output is correct
5 Correct 102 ms 14832 KB Output is correct
6 Correct 104 ms 14824 KB Output is correct
7 Correct 77 ms 14760 KB Output is correct
8 Correct 96 ms 14748 KB Output is correct
9 Correct 124 ms 14676 KB Output is correct
10 Correct 98 ms 14864 KB Output is correct
11 Correct 133 ms 14296 KB Output is correct
12 Correct 82 ms 14408 KB Output is correct
13 Correct 112 ms 14680 KB Output is correct
14 Incorrect 84 ms 14376 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6596 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 Incorrect 14 ms 6636 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -