Submission #784255

#TimeUsernameProblemLanguageResultExecution timeMemory
784255OzyHighway Tolls (IOI18_highway)C++17
51 / 100
219 ms262144 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define pll pair<lli,lli> #define MAX 90000 //para los hijos #define des first #define id second lli m,df,sz,prof; lli arista_padre[MAX+2],tam[MAX+2],color[MAX+2]; vector<pll> hijos[MAX+2]; vector<lli> nodos,inval; vector<int> status; void pre_process(lli pos, lli padre) { tam[pos] = 1; for(auto h : hijos[pos]) { if(padre == h.des || inval[h.id] == 1) continue; pre_process(h.des,pos); tam[pos] += tam[h.des]; } } lli busca(lli pos, lli padre, lli lim) { for(auto h : hijos[pos]) { if (padre == h.des || inval[h.id] == 1) continue; if (tam[h.des] > lim) return busca(h.des,pos,lim); } return pos; } void marca(lli pos, lli padre, lli ari, lli c) { status[ari] = c; color[ari] = c; for(auto h : hijos[pos]) { if (h.des == padre || inval[h.id] == 1) continue; marca(h.des,pos,h.id,c); } } void dfs(lli pos, lli padre, lli p,lli c) { if(p == prof) { nodos.push_back(pos); return; } for(auto h : hijos[pos]) { if(padre == h.des || color[h.id] != c || inval[h.id] == 1) continue; arista_padre[h.des] = h.id; dfs(h.des,pos,p+1,c); } } lli solve(lli raiz, lli c) { if(prof == 0) return raiz; nodos.clear(); rep(i,0,m-1) status[i] = 0; dfs(raiz,-1,0,c); lli last,ini = 0; lli mitad,fin = nodos.size()-1; while (ini <= fin) { mitad = (ini+fin)/2; rep(i,0,nodos.size()-1) { if (ini <= i && i <= mitad) status[ arista_padre[nodos[i]] ] = 1; else status[arista_padre[nodos[i]]] = 0; } lli x = ask(status); if (x != df) { fin = mitad-1; last = mitad; } else ini = mitad+1; } return(nodos[last]); } void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) { m = u.size(); rep(i,0,m-1) { hijos[u[i]].push_back({v[i],i}); hijos[v[i]].push_back({u[i],i}); } status.resize(m,0); inval.resize(m,0); df = ask(status); sz = df/A; //busca centroid lli raiz = 0; lli p0,p1; do { pre_process(raiz,-1); if(tam[raiz] == 2) { for(auto h : hijos[raiz]) { if (inval[h.id] == 0) answer(raiz,h.des); return; } } lli mitad = tam[raiz]/2; lli act = busca(raiz,-1,mitad); //dividelo en los 2 colores lli unos = 0; rep(i,0,m-1) { status[i] = 0; color[i] = 2; } for(auto h : hijos[act]) { if (inval[h.id] == 1) continue; lli gh; if(tam[h.des] > tam[act]) gh = tam[raiz]-tam[act]; else gh = tam[h.des]; if (gh+unos <= mitad) { marca(h.des,act,h.id,1); unos += gh; } else { //debug("entro"); marca(h.des,act,h.id,0); } } //corregido lli x = ask(status); lli bigg = (x - df)/(B-A); raiz = act; if (bigg == sz) rep(i,0,m-1) { //debug("entre con sz"); if(color[i] == 0) inval[i] = 1; } else if (bigg == 0) { //debug("entre con 0"); rep(i,0,m-1) if(color[i] == 1) inval[i] = 1; } else { p1 = bigg; p0 = sz-bigg; break; } //debug(raiz); //rep(i,0,m-1) { // debugsl(i); // debugsl(color[i]); // debug(inval[i]); //} } while(true); //debug(raiz); //debug(p0); //debug(p1); //pregunta por ambas raices y reporta el resultado prof = p0; lli x = solve(raiz,0); prof = p1; lli y = solve(raiz,1); //debugsl(x); //debug(y); answer(x,y); }

Compilation message (stderr)

highway.cpp: In function 'long long int solve(long long int, long long int)':
highway.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,a,b) for(int i = (a); i <= (b); i++)
      |                                       ^
highway.cpp:75:9: note: in expansion of macro 'rep'
   75 |         rep(i,0,nodos.size()-1) {
      |         ^~~
highway.cpp:88:22: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     return(nodos[last]);
      |                      ^
#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...