Submission #1199734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199734		ricardsjansons	Race (IOI11_race)	C++20	9 / 100	1060 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>,vector<int>>mem;

vector<int>dfs(int u,int p=-1){
    if(mem.count({u,p})){
        return mem[{u,p}];
    }
    mem[{u,p}].resize(KMAX+1);
    vector<int>&res=mem[{u,p}];
    for(auto[v,l]:adj[u]){
        if(v==p){
            continue;
        }
        vector<int>x=dfs(v,u);
        for(int i=l;i<=KMAX;i++){
            if(i-l>0&&!x[i-l]){
                continue;
            }
            res[i]=better(res[i],x[i-l]+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++){
        res=better(res,dfs(u)[K]);
    }
    return (res?res:-1);
}

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