Submission #1210325

#TimeUsernameProblemLanguageResultExecution timeMemory
1210325loiiii12358Highway Tolls (IOI18_highway)C++20
12 / 100
60 ms9768 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define int long long int val,dep,s=0,e; vector<int32_t> vec; vector<pair<int,int>> pos; vector<vector<pair<int,int>>> edges; void run(int now,int par,int d){ for(int i=0;i<edges[now].size();i++){ if(edges[now][i].first==par){ continue; }else if(d==dep-1){ pos.push_back(edges[now][i]); }else{ run(edges[now][i].first,now,d+1); } } } int search(int l,int r){ if(l==r){ return l; } int m=(l+r)/2; fill(vec.begin(),vec.end(),0); for(int i=0;i<=m;i++){ vec[pos[i].second]=1; } if(ask(vec)!=val){ return search(l,m); } return search(m+1,r); } void find_pair(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A, int32_t B) { edges.resize(N); for(int i=0;i<U.size();i++){ edges[U[i]].push_back({V[i],i}); edges[V[i]].push_back({U[i],i}); } vec.resize(U.size(),0); val=ask(vec); dep=val/A; run(0,-1,0); // cout << val << ' ' << dep << '\n'; answer(0,pos[search(0,pos.size()-1)].first); }
#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...