Submission #787114

#TimeUsernameProblemLanguageResultExecution timeMemory
787114APROHACKHighway Tolls (IOI18_highway)C++17
51 / 100
130 ms16320 KiB
#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; 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, 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 (stderr)

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 ++){
      |                   ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...