Submission #1055217

#TimeUsernameProblemLanguageResultExecution timeMemory
1055217Ahmed57Highway Tolls (IOI18_highway)C++17
51 / 100
105 ms14332 KiB
#include "bits/stdc++.h" #include "highway.h" using namespace std; #define int long long pair<int,int> p[100001]; int dep[100001]; vector<pair<int,int>> adj[100001]; void dfs(int i,int pr,int id){ queue<int> q; q.push(0); dep[0] = 1; while(!q.empty()){ int f = q.front();q.pop(); for(auto j:adj[f]){ if(dep[j.first]==0){ dep[j.first] = dep[f]+1; p[j.first] = {f,j.second}; q.push(j.first); } } } } void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B){ int m = U.size(); vector<int32_t> as(m,0); vector<int32_t> as2(m,1); int len = ask(as); int len2 = ask(as2); for(int i = 0;i<U.size();i++){ adj[U[i]].push_back({V[i],i}); adj[V[i]].push_back({U[i],i}); } dfs(0,0,-1); vector<pair<int,int>> v; for(int i = 0;i<N;i++){ v.push_back({dep[i],i}); } sort(v.begin(),v.end()); reverse(v.begin(),v.end()); int l = 0 , r = v.size()-2 , ans = 0; while(l<=r){ int mid = (l+r)/2; vector<int32_t> as(m,0); for(int i = 0;i<=mid;i++){ as[p[v[i].second].second] = 1; } if(ask(as)!=len){ ans = mid; r = mid-1; }else l = mid+1; } int a = v[ans].second; l = 2 , r = dep[a] ;int ans2 = -1; while(l<=r){ int mid = (l+r)/2; vector<int32_t> as(m,0); for(int i = 0;i<N;i++){ if(dep[i]>=mid){ as[p[i].second] =1 ; } } int na = ask(as); if(na==len2){ ans2 = mid; l = mid+1; }else r = mid-1; } assert(ans2!=-1); ans2--; if((dep[a]-ans2)*A==len){ int x = len/A; int b = a; while(x--){ b = p[b].first; } answer(a,b); return ; } vector<int> lol; l = 0; for(int i = 0;i<v.size();i++){ if(v[i].second==a)l = i; if(v[i].first>ans2)r = i; } int ans3 = -1; while(l<=r){ int mid = (l+r)/2; vector<int32_t> as(m,0); for(int i = 0;i<=mid;i++){ as[p[v[i].second].second] = 1; } int f = a; while(dep[f]>v[mid].first)f = p[f].first; as[p[f].second] = 1; if(ask(as)>=len+(dep[a]-v[mid].first+1)*(B-A)+(B-A)){ ans3 = mid; r = mid-1; }else l = mid+1; } //assert(ans3!=-1); if(ans3==-1){ assert(0); } int b = v[ans3].second; answer(a,b); }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0;i<U.size();i++){
      |                   ~^~~~~~~~~
highway.cpp:83:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0;i<v.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...