Submission #1272479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272479		dangheo	Race (IOI11_race)	C++20	21 / 100	3093 ms	24496 KiB

race

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include "race.h"

#define hyathu main
#define popcorn __builtin_popcount

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int mmb = 1e5 + 69;
const ld pi = atan(1) * 4;

vector <pair <int, ll>> v[mmb];
int p[mmb];
map <ll, int> dist[mmb];
ll d[mmb], K;
int h[mmb];
int ans = 2e9;

void dfs(int i){
    map <ll, int> &cur = dist[i];
    cur.emplace(d[i], h[i]);
    
    for(pair <int, ll> &adj : v[i]){
        int nx = adj.first;
        ll ad = adj.second;
        if(nx == p[i]) continue;
        
        p[nx] = i;
        d[nx] = d[i] + ad;
        h[nx] = h[i] + 1;
        dfs(nx);
        
        for(pair <const ll, int> &dst : dist[nx]){
            ll ds = dst.first;
            int hs = dst.second;
            auto it = cur.find(K - ds + 2 * d[i]);
            if(it != cur.end())
                ans = min(ans, hs + it->second - 2 * h[i]);
        }
        
        for(pair <const ll, int> &dst : dist[nx]){
            ll ds = dst.first;
            int hs = dst.second;
            auto res = cur.insert(dst);
            if(!res.second) res.first->second = min(res.first->second, hs);
        }
        
        dist[nx].clear();
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    fill(p, p + n, -1);
    
    K = k;
    for(int i = 0; i < n - 1; ++i){
        v[h[i][0]].emplace_back(h[i][1], l[i]);
        v[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    
    dfs(0);
    return (ans == 2e9 ? -1 : ans);
}

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