Submission #888323

#	Time	Username	Problem	Language	Result	Execution time	Memory
888323		ash_gamertable	Race (IOI11_race)	C++14	0 / 100	1 ms	2392 KiB

race

#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"
using namespace std;

long long ans=1e18;
vector<vector< pair<long long,long long> > > g;// {node,dist}
vector<long long> off,offset_node;
void dfs(long long node,long long par,vector<map<long long,long long> > &hash,long long k)
{
    for(auto child:g[node])
    {
        if(child.first==par) continue;
        dfs(child.first,node,hash,k);
    // }
    // for(auto child:g[node])
    // {
        if(child.first == par) continue;
        long long off_node = off[node],off_child=off[child.first],edge=child.second,off_used=off_child;
         long long 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] = ll+ 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++)
        {
            long long dist = it->first + off_used + edge;
            long long 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]);
            else if(k-dist-off[node]) ans =min(ans,mn_nodes+ offset_node[node]);
            if(hash[node].find(dist-off[node])!=hash[node].end())
            {
                long long 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[])
{
  long long n,k,a,b,wt;
  vector<map<long long,long long> > hash;
  n=N;
  k=K;
   g.resize(n+10);
    off.assign(n+10,0);
    offset_node.assign(n+10,0);
    for(long long 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(long long i=0;i<=n;i++) hash[i][0]=0;
    dfs(0,-1,hash,k);
    if(ans==1e18) ans=-1;
    int ans2=ans;
  return ans2;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(long long int, long long int, std::vector<std::map<long long int, long long int> >&, long long int)':
race.cpp:86:19: warning: unused variable 'off_node' [-Wunused-variable]
   86 |         long long off_node = off[node],off_child=off[child.first],edge=child.second,off_used=off_child;
      |                   ^~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57