Submission #1199683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199683		ricardsjansons	Race (IOI11_race)	C++20	9 / 100	1235 ms	327680 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int INF=1e9;

int better(int a,int b){
    if(!a){
        return b;
    }
    if(!b){
        return a;
    }
    return min(a,b);
}

int KMAX;
vector<vector<pair<int,int>>>adj;
map<pair<int,int>,map<int,int>>mem;

map<int,int>dfs(int u,int p){
    if(mem.count({u,p})){
        return mem[{u,p}];
    }
    map<int,int>&res=mem[{u,p}];
    res[0]=0;
    for(auto[v,l]:adj[u]){
        if(v==p){
            continue;
        }
        for(auto[s,c]:dfs(v,u)){
            if(s+l>KMAX){
                continue;
            }
            res[s+l]=better(res[s+l],c+1);
        }
    }
    return res;
}

int best_path(int N, int K, int H[][2], int L[])
{
    KMAX=K;
    adj.resize(N);
    for(int i=0;i<N-1;i++){
        auto[u,v]=H[i];
        int l=L[i];
        adj[u].push_back({v,l});
        adj[v].push_back({u,l});
    }
    int res=0;
    for(int u=0;u<N;u++){
        for(auto[v,l]:adj[u]){
            //cout<<"! "<<u<<" "<<v<<" "<<dfs(v,u)[K]<<"\n";
            res=better(res,dfs(v,u)[K]);
        }
    }
    return (res?res:-1);
}

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