oj.uz

Submission #784213

# Submission time Handle Problem Language Result Execution time Memory
784213 2023-07-15T21:08:13 Z APROHACK Highway Tolls (IOI18_highway) C++14
12 / 100
 118 ms 13324 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;
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;
	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);
	}
	vector<int>w;
	for(int i = 0 ; i < m ; i ++)w.pb(0);
	ll ans = ask(w);
	largo = ans / A;
	
	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 ++){
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5456 KB Output is correct
2 Correct 3 ms 5404 KB Output is correct
3 Correct 3 ms 5456 KB Output is correct
4 Correct 2 ms 5396 KB Output is correct
5 Correct 2 ms 5396 KB Output is correct
6 Correct 2 ms 5400 KB Output is correct
7 Correct 2 ms 5396 KB Output is correct
8 Correct 2 ms 5436 KB Output is correct
9 Correct 2 ms 5456 KB Output is correct
10 Correct 2 ms 5404 KB Output is correct
11 Correct 2 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 5476 KB Output is correct
2 Correct 9 ms 6308 KB Output is correct
3 Correct 89 ms 13240 KB Output is correct
4 Correct 114 ms 13292 KB Output is correct
5 Correct 94 ms 13236 KB Output is correct
6 Correct 81 ms 13200 KB Output is correct
7 Correct 113 ms 13216 KB Output is correct
8 Correct 94 ms 13324 KB Output is correct
9 Correct 103 ms 13128 KB Output is correct
10 Correct 72 ms 13296 KB Output is correct
11 Correct 86 ms 12992 KB Output is correct
12 Correct 89 ms 13000 KB Output is correct
13 Correct 99 ms 12928 KB Output is correct
14 Correct 118 ms 12996 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6280 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5456 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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