Submission #1098553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098553		BLOBVISGOD	Race (IOI11_race)	C++17	0 / 100	13 ms	19548 KiB

race

#include "bits/stdc++.h"
#include "race.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int Nmax = 2e5+10, oo = 1e9;
int cc = 0;
map<ll,int> mps[Nmax]; // min dist, node id

struct state{
    int min_edge = oo;

    ll offset_dist = 0, offset_edges = 0;
    int map_id;

    state(int at){
        mps[cc][0] = 0;
        map_id = cc++;
    }
    state(){
        map_id = Nmax-1;
    }

    void prop(int len){
        offset_edges++;
        offset_dist+=len;
    }
};

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<int,ll>>> adj(N);
    rep(i,0,N-1){
        int u = H[i][0], v = H[i][1];
        u--,v--;
        adj[u].push_back({v,L[i]});
        adj[v].push_back({u,L[i]});
    }

    vi vis(N);

    auto dfs = [&](int at, auto&& dfs) -> state {
        vis[at] = 1;
        if (sz(adj[at]) == 1 and vis[adj[at][0].first]) return state(at); // leaf

        state my;
        bool frst = 1;
        for(auto [to,d] : adj[at]) if (!vis[to]){
            if (frst){
                my = dfs(to,dfs);
                my.prop(d);
                frst = 0;
            }else{
                auto ot = dfs(to,dfs);
                ot.prop(d);

                // merge
                if (sz(mps[ot.map_id]) > sz(mps[my.map_id])) swap(ot,my);

                ll diff = ot.offset_dist - my.offset_dist;
                ll diffedges = ot.offset_edges - my.offset_edges;

                if (ot.min_edge < my.min_edge){ // update best until now
                    my.min_edge = ot.min_edge;
                }

                // find new best
                for(auto [k,v] : mps[ot.map_id]){
                    int finddist = K-k-ot.offset_dist-my.offset_dist;
                    if (mps[my.map_id].count(finddist)){
                        auto ret = mps[my.map_id][finddist];
                        int newedge = my.offset_edges + ot.offset_edges + v + ret;
                        if (newedge < my.min_edge){
                            my.min_edge = newedge;
                        }
                    } 
                }

                // merge
                for(auto [k,v] : mps[ot.map_id]){
                    ll newdist = k + diff;
                    int newedge = v + diffedges;
                    if (mps[my.map_id].count(newdist)){
                        auto& ret = mps[my.map_id][newdist];
                        if (ret > newedge){
                            ret = newedge;
                        }
                    }else{
                        mps[my.map_id][newdist] = newedge;
                    }
                }
            }
        }

        return my;
    };

    auto ret = dfs(0,dfs);

    if (ret.min_edge == oo) return -1;
    else return ret.min_edge; 


}

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