Submission #1150901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150901		lidplf	Race (IOI11_race)	C++20	43 / 100	236 ms	72872 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define MOD2 998244353
using namespace std;
int best_path(int n, int k, int H[][2], int L[])
{
    vector<vector<pair<ll,ll>>> g(n);
    for (int i = 0; i < n - 1; i++){
        g[H[i][0]].emplace_back(make_pair(H[i][1],L[i]));
        g[H[i][1]].emplace_back(make_pair(H[i][0],L[i]));
    }
    int res = INT_MAX;
    vector<map<ll,int>> dist(n);
    //dist(x) + dist(y) - 2*dist(z) = k
    //k+2*dist(z) = dist(x) + dist(y)
    //dist(y) = k+2*dist(z)-dist(x)
    auto dfs = [&] (auto&& self, int node, int parent, int depth, ll p) -> void{
        for (auto [neighbor, weight]: g[node]){
            if (neighbor!=parent){
                self(self,neighbor,node,depth+1,p+weight);
                if (dist[neighbor].count(p+k)){
                    res = min(res, dist[neighbor][p+k] - depth);
                }
                if (dist[neighbor].size() > dist[node].size()) swap(dist[node], dist[neighbor]);
                for (auto [pref, dep]: dist[neighbor]){
                    if (dist[node].count(k+2*p-pref)){
                        res = min(res, dist[node][k+2*p-pref] + dep - 2*depth);
                    }
                    if (!dist[node].count(pref)){
                        dist[node][pref] = dep;
                    }
                    else{
                        dist[node][pref] = min(dist[node][pref], dep);
                    }
                }
            }
        }
        dist[node][p] = depth;
    };
    dfs(dfs,0,0,0,0);
    if (res==INT_MAX){
      return -1;
    }
    return res;
}

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