Submission #888272

#	Time	Username	Problem	Language	Result	Execution time	Memory
888272		ash_gamertable	Race (IOI11_race)	C++14	0 / 100	1 ms	2396 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;

int ans=1e9;
vector<vector< pair<int,int> > > g;// {node,dist}
vector<int> off;
void dfs(int node,int par,vector<map<int,int> > &hash,int k)
{
    //cerr<<node<<" * "<<par<<"\n";
    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;
        if(hash[node].size()<hash[child.first].size())
        {
            // cout<<node<<"*\n";
            off_used = off[node];
            off[node] = off_child+edge;
            edge=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 = it->second;
            if(hash[node].find(k-dist-off[node])!=hash[node].end())
            ans=min(ans,mn_nodes+hash[node][k-dist-off[node]]);
            if(hash[node].find(dist-off[node])!=hash[node].end())
            {
                int v1 = hash[node][dist-off[node]];
                hash[node][dist-off[node]] = min(v1,1+mn_nodes);
            }
            else hash[node][dist-off[node]] = 1+mn_nodes;
        }
        
    }
    // if(node==2)
    //     {
    //         for(auto it=hash[node].begin();it!=hash[node].end();it++){
    //             cout<<it->first<<" "<<it->second<<"\n";
    //         }
    //         cout<<off[node]<<"\n";
    //     }
    // cerr<<node<<" "<<ans<<"\n";

}
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);
    for(int i=0;i<=n-2;i++){
        a=H[i][0];
        b=H[i][1];
        wt=L[i];
        a++;b++;
        g[a].push_back(make_pair(b,wt));
        g[b].push_back(make_pair(a,wt));
    }
    hash.resize(n+10);
    for(int i=1;i<=n;i++) hash[i][0]=1;
    dfs(1,0,hash,k);
    if(ans==1 || ans==1e9) ans=0;
    ans--;
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, std::vector<std::map<int, int> >&, int)':
race.cpp:87:13: warning: unused variable 'off_node' [-Wunused-variable]
   87 |         int 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