Submission #1154969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154969		bronze_coder	Race (IOI11_race)	C++20	100 / 100	516 ms	124180 KiB

race

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

int best_path(int n,int k,int h[][2],int l[]){
    vector<vector<pair<int,int>>> adj(n);
    for(int i=0;i<n-1;i++){
        int a = h[i][0];
        int b = h[i][1];
        adj[a].push_back({b,l[i]});
        adj[b].push_back({a,l[i]});
    }
    vector<int> q(1,0);
    vector<int> parent(n,-1);
    vector<int> dist(n,0);
    vector<long long> len(n,0);
    for(int i=0;i<n;i++){
        int a = q[i];
        for(auto j:adj[a]){
            if(j.first!=parent[a]){
                parent[j.first] = a;
                q.push_back(j.first);
                dist[j.first] = dist[a]+1;
                len[j.first] = len[a]+j.second;
            }
        }
    }
    vector<map<long long,int>> v(n);
    for(int i=0;i<n;i++){
        v[i][len[i]] = dist[i];
    }
    int ans = n;
    for(int j=n-1;j>0;j--){
        int i = q[j];
        int m = parent[i];
        if(v[m].size()<v[i].size()){
            swap(v[m],v[i]);
        }
        v[i][len[m]] = dist[m];
        for(auto z:v[i]){
            if(v[m].find(2*len[m]-z.first+k)!=v[m].end()){
                ans = min(ans,v[m][2*len[m]-z.first+k]+z.second-2*dist[m]);
            }
        }
        for(auto z:v[i]){
            if(v[m][z.first]==0){
                v[m][z.first] = v[i][z.first];
            }
            else{
                v[m][z.first] = min(v[m][z.first],v[i][z.first]);
            }
        }
    }
    if(ans==n){
        return -1;
    }
    return ans;
}

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