Submission #556271

#	Time	Username	Problem	Language	Result	Execution time	Memory
556271		n0sk1ll	Race (IOI11_race)	C++17	0 / 100	9 ms	17492 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define xx first
#define yy second

using namespace std;
long long int typedef li;

vector<vector<pair<int,int>>> g(200005);
int ch[200005],ans=1e9;

struct offmap
{
    map<li,int> mapa;
    li key_offset=0;
    int value_offset=0;

    void add(int x, int k)
    {
        auto it=mapa.find(x-key_offset);
        if (it==mapa.end()) mapa[x-key_offset]=k-value_offset;
        else it->yy=min(it->yy,k-value_offset);
    }

    int find(int x)
    {
        auto it=mapa.find(x-key_offset);
        if (it==mapa.end()) return 1e9;
        return it->yy+value_offset;
    }

    void uproot(int w)
    {
        key_offset+=w;
        value_offset++;
    }

    vector<pair<int,int>> iter()
    {
        vector<pair<int,int>> ret;
        for (auto it : mapa) ret.push_back({it.xx+key_offset,it.yy+value_offset});
        return ret;
    }
} dub[200005];
int gde[200005];

int K;
void dfs(int p, int q)
{
    gde[p]=p;
    for (auto [it,w] : g[p]) if (it!=q)
    {
        dfs(it,p);
        if (ch[gde[it]]>ch[gde[p]]) gde[p]=gde[it];
        ch[p]+=ch[it];
    }
    for (auto [it,w] : g[p]) if (it!=q) dub[gde[it]].uproot(w);
    dub[gde[p]].add(0,0);
    for (auto [it,w] : g[p]) if (it!=q && it!=gde[p])
    {
        vector<pair<int,int>> tmp=dub[gde[it]].iter();
        for (auto it : tmp) ans=min(ans,it.yy+dub[gde[p]].find(K-it.xx));
        for (auto it : tmp) dub[gde[p]].add(it.xx,it.yy);
    }

    ans=min(ans,dub[gde[p]].find(K));

    /*cout<<p<<": "<<endl;
    vector<pair<int,int>> tmp=dub[gde[p]].iter();
    for (auto it : tmp) cout<<it.xx<<": "<<it.yy<<endl;
    cout<<endl;*/
}

int best_path(int n, int k, int H[][2], int L[])
{
    for (int i=0;i<n-1;i++) g[H[i][0]].push_back({H[i][1],L[i]}),g[H[i][1]].push_back({H[i][0],L[i]});
    for (int i=0;i<n;i++) ch[i]=1;
    K=k,dfs(0,-1); return (ans==1e9?-1:ans);
}

/*

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7

*/

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