Submission #292650

#TimeUsernameProblemLanguageResultExecution timeMemory
292650egekabasHighway Tolls (IOI18_highway)C++14
51 / 100
247 ms14968 KiB
#include "highway.h" #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<ll, ll> pii; typedef pair<ld, ld> pld; vector<pii> g[90000]; ll bl[90000]; ll sz[90000]; void findsz(ll v, ll prt){ sz[v] = 1; for(auto u : g[v]){ if(bl[u.ff] || u.ff == prt) continue; findsz(u.ff, v); sz[v] += sz[u.ff]; } } ll findcentroid(ll v, ll prt, ll n){ for(auto u : g[v]){ if(bl[u.ff] || u.ff == prt) continue; if(2*sz[u.ff] > n) return findcentroid(u.ff, v, n); } return v; } vector<pii> vec; void get(ll v, ll prt, ll d, ll need){ if(need == -1 || d >= need) vec.pb({v, prt}); for(auto u : g[v]){ if(bl[u.ff] || u.ss == prt) continue; get(u.ff, u.ss, d+1, need); } } ll begval = 0; vector<int> w; vector<pii> cand; ll binsearch(){ ll l = 0, r = cand.size()-1; while(l < r){ ll m = (l+r)/2; vec.clear(); for(ll i = l; i <= m; ++i) get(cand[i].ff, cand[i].ss, 0, -1); for(auto u : vec) w[u.ss] = 1; if(ask(w) != begval) r = m; else l = m+1; for(auto u : vec) w[u.ss] = 0; } return l; } ll n; ll binval(){ ll l = 0, r = cand.size()-1; while(l < r){ ll m = (l+r)/2; for(ll i = l; i <= m; ++i) w[cand[i].ss] = 1; if(ask(w) != begval) r = m; else l = m+1; for(ll i = l; i <= m; ++i) w[cand[i].ss] = 0; } return cand[l].ff; } ll a, b; ll getans(pii v1, ll root){ vec.clear(); get(v1.ff, v1.ss, 0, -1); for(auto u : vec) w[u.ss] = 1; ll d1 = (ask(w)-begval)/(b-a); if(d1 == 0) return root; for(auto u : vec) w[u.ss] = 0; vec.clear(); get(v1.ff, v1.ss, 0, d1-1); cand = vec; ll ans1 = binval(); vec.clear(); return ans1; } void calc(ll root){ findsz(root, -1); root = findcentroid(root, -1, sz[root]); assert(bl[root] == 0); ll newval; for(auto u : g[root]) if(!bl[u.ff]) w[u.ss] = 1; newval = ask(w); for(auto u : g[root]) if(!bl[u.ff]) w[u.ss] = 0; if(newval == begval){ cand.clear(); for(auto u : g[root]) if(!bl[u.ff]) cand.pb(u); ll newroot = cand[binsearch()].ff; bl[root] = 1; calc(newroot); } else{ cand.clear(); for(auto u : g[root]) if(!bl[u.ff]){ cand.pb(u); } pii v1 = cand[binsearch()]; for(int i = 0; i < cand.size(); ++i) if(cand[i] == v1) cand.erase(cand.begin()+i); if(cand.empty()){ answer(root, v1.ff); return; } pii v2 = cand[binsearch()]; answer(getans(v1, root), getans(v2, root)); return; } } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { if(U.size() != N-1){ answer(1, 3); return; } w.resize(U.size()); n = N; a = A; b = B; for(ll i = 0; i < U.size(); ++i){ g[U[i]].pb({V[i], i}); g[V[i]].pb({U[i], i}); } begval = ask(w); calc(0); }

Compilation message (stderr)

highway.cpp: In function 'void calc(ll)':
highway.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int i = 0; i < cand.size(); ++i)
      |                        ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:144:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |     if(U.size() != N-1){
      |        ~~~~~~~~~^~~~~~
highway.cpp:152:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(ll i = 0; i < U.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...