Submission #888275

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

race

#include<bits/stdc++.h>
#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)
{
    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())
        {
            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;
        }
        
    }

}
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-1;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:18:13: warning: unused variable 'off_node' [-Wunused-variable]
   18 |         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