| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 888310 | ash_gamertable | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
// C++
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include "race.h"
#define int long long
using namespace std;
int ans=1e9;
vector<vector< pair<int,int> > > g;// {node,dist}
vector<int> off,offset_node;
void dfs(int node,int par,vector<map<int,int> > &hash,int k)
{
for(auto x:g[node])
{
if(x.first==par) continue;
dfs(x.first,node,hash,k);
}
for(auto child:g[node])
{
if(child.first == par) continue;
int off_node = off[node],off_child=off[child.first],edge=child.second,off_used=off_child;
int offset_node_used = offset_node[child.first],ll=1;
if(hash[node].size()<hash[child.first].size())
{
// cout<<node<<"*\n";
off_used = off[node];
offset_node_used = offset_node[node];
off[node] = off_child+edge;
offset_node[node] = 1+ offset_node[child.first];
edge=0;
ll=0;
swap(hash[node],hash[child.first]);
}
for(auto it=hash[child.first].begin();it!=hash[child.first].end();it++)
{
int dist = it->first + off_used + edge;
int mn_nodes = ll+it->second+offset_node_used;
if(hash[node].find(k-dist-off[node])!=hash[node].end())
ans=min(ans,mn_nodes+hash[node][k-dist-off[node]] + offset_node[node]);
if(hash[node].find(dist-off[node])!=hash[node].end())
{
int v1 = hash[node][dist-off[node]]+offset_node[node];
hash[node][dist-off[node]] = min(v1,mn_nodes)-offset_node[node];
}
else hash[node][dist-off[node]] = mn_nodes-offset_node[node];
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
int n,k,a,b,wt;
vector<map<int,int> > hash;
n=N;
k=K;
g.resize(n+10);
off.assign(n+10,0);
offset_node.assign(n+10,0);
for(int i=0;i<n-1;i++){
a=H[i][0];
b=H[i][1];
wt=L[i];
g[a].push_back(make_pair(b,wt));
g[b].push_back(make_pair(a,wt));
}
hash.resize(n+10);
for(int i=0;i<=n;i++) hash[i][0]=0;
dfs(0,-1,hash,k);
if(ans==1e9) ans=-1;
return ans;
}