#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[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 << " " ;
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:144:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 0 ; i < nodos.size() ; i ++){
| ~~^~~~~~~~~~~~~~
| # |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5596 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6480 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5596 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
6464 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
6480 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
