oj.uz

Submission #787126

# Submission time Handle Problem Language Result Execution time Memory
787126 2023-07-18T20:52:05 Z APROHACK Highway Tolls (IOI18_highway) C++17
51 / 100
 132 ms 15832 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];
int keepBanned;


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;
	ll tried[130003];
	for(int i = 0 ; i < m ; i ++)tried[i] = -1;
	while(li + 1 < ls){
		llenar(0, m-1, 0, w);
		llenar(0, keepBanned-1, 1, 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 other, int ban, 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(other);
	cola.push(dd);
	dist[dd] = 0;
	bool vis[n+1];
	bool search[n+1];
	bool banned[m+1];
	memset(vis, false, sizeof vis);
	memset(search, false, sizeof search);
	memset(banned, false, sizeof banned);
	banned[ban] = true;
	vis[dd] = true;
	vis[other] = true;
	search[dd] = true;
	while(!cola.empty()){
		int cur = cola.front();
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(banned[idx[cur][i]] or idx[cur][i] < keepBanned)continue;
			if(vis[adj[cur][i]])continue;
			vis[adj[cur][i]] = true;
			if(search[cur]){
				search[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]);
			}else{
				cola.push(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);
		llenar(0, keepBanned -1 , 1, 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);
	keepBanned = ejeMedio;
	//cout << ejeMedio << endl;
	//cout << U[ejeMedio] << " " << V[ejeMedio] << endl;
	
	
	vector<int>distancias, nodos, ejes;
	ejes = getEdjes(V[ejeMedio], U[ejeMedio], ejeMedio, distancias, nodos);
	llenar(0, m-1, 0, w);
	llenar(0, keepBanned-1, 1, 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], V[ejeMedio], ejeMedio, distancias, nodos);
	llenar(0, m-1, 0, w);
	llenar(0, keepBanned-1, 1, 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, int, std::vector<int>&, std::vector<int>&)':
highway.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   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:141:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for(int i = 0 ; i < nodos.size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~
highway.cpp:164:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   for(int i = 0 ; i < nodos.size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 9 ms 6988 KB Output is correct
3 Correct 128 ms 15232 KB Output is correct
4 Correct 95 ms 15288 KB Output is correct
5 Correct 132 ms 15280 KB Output is correct
6 Correct 124 ms 14704 KB Output is correct
7 Correct 83 ms 14640 KB Output is correct
8 Correct 124 ms 15272 KB Output is correct
9 Correct 113 ms 14692 KB Output is correct
10 Correct 100 ms 14760 KB Output is correct
11 Correct 110 ms 14132 KB Output is correct
12 Correct 125 ms 14696 KB Output is correct
13 Correct 102 ms 14880 KB Output is correct
14 Correct 102 ms 14832 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6992 KB Output is correct
2 Correct 17 ms 8136 KB Output is correct
3 Correct 28 ms 8616 KB Output is correct
4 Correct 62 ms 14516 KB Output is correct
5 Correct 105 ms 14568 KB Output is correct
6 Correct 100 ms 14864 KB Output is correct
7 Correct 85 ms 14052 KB Output is correct
8 Correct 96 ms 14612 KB Output is correct
9 Correct 63 ms 14296 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 9 ms 6992 KB Output is correct
3 Correct 72 ms 13168 KB Output is correct
4 Correct 86 ms 15280 KB Output is correct
5 Correct 80 ms 14316 KB Output is correct
6 Correct 80 ms 14380 KB Output is correct
7 Correct 94 ms 14644 KB Output is correct
8 Correct 107 ms 14260 KB Output is correct
9 Correct 119 ms 15120 KB Output is correct
10 Correct 114 ms 14640 KB Output is correct
11 Correct 87 ms 14872 KB Output is correct
12 Correct 129 ms 14564 KB Output is correct
13 Correct 117 ms 14412 KB Output is correct
14 Correct 114 ms 14168 KB Output is correct
15 Correct 73 ms 14308 KB Output is correct
16 Correct 110 ms 14380 KB Output is correct
17 Correct 124 ms 14792 KB Output is correct
18 Correct 105 ms 14884 KB Output is correct
19 Correct 116 ms 14432 KB Output is correct
20 Correct 105 ms 14136 KB Output is correct
21 Correct 93 ms 15640 KB Output is correct
22 Correct 103 ms 15024 KB Output is correct
23 Correct 94 ms 15652 KB Output is correct
24 Correct 87 ms 15832 KB Output is correct
25 Correct 114 ms 15124 KB Output is correct

Subtask #5
0 / 18.0

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