Submission #1185873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185873		ema_nicole	Race (IOI11_race)	C++17	100 / 100	943 ms	43500 KiB

race

#pragma GCC optimize ("Ofast", "unroll-loops")
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>

using namespace std;
const int NMAX = 200002;
const int INF = 1e9;

struct muchii {
    int nod, dist;
};
vector <vector <muchii>> v;
int n, k;
bool f[NMAX]; ///dc deja am procesat ca centroid respectivul sau nu

int parent[NMAX];
int weight[NMAX]; ///ce weight are subarb resp

void dfssize(int start) {
    weight[start] = 1;
    for(const auto& x : v[start]) {
        if(x.nod == parent[start] || f[x.nod])
            continue;
        parent[x.nod] = start;
        dfssize(x.nod);
        weight[start] += weight[x.nod];
    }
}

int centroid = -1;

bool dfscentroid(int start, int tot) { ///sizeul e de sus
    bool ok = false;
    if(tot - weight[start] > tot / 2)
        ok = 1;
    for(const auto& x : v[start]) {
        if(x.nod == parent[start] || f[x.nod])
            continue;
        if(weight[x.nod] > tot / 2)
            ok = true;
    }
    if(!ok) { ///am gasit centroidul
        centroid = start;
        return true;
    }
    for(const auto& x : v[start]) {
        if(x.nod == parent[start] || f[x.nod])
            continue;
        if (dfscentroid(x.nod, tot)) {
            return true;
        }
    }
    return false;
}

map <int, int> umap, full; ///full pt centroid, umap pt fiul curent
int ans = INF; ///dist minima pt suma k

void updateans(int copil) { ///start e copilul, actually

    if(umap.find(k) != umap.end()) ///dc deja e lant pana in el
        ans = min(ans, umap[k]);

    for(const auto& var : umap) { ///ce val am pastrat in copil
        if(var.second > ans)
            continue;
        ///COMPARAM cu ce avem de la vechii fii
        if(full.find(k - var.first) != full.end())
            ans = min(ans, full[k - var.first] + var.second);
    }
    for(const auto& var : umap) { ///UPDATAM
        if(var.first > k || var.second > ans)
            continue;
        if(full.find(var.first) != full.end())
            full[var.first] = min(full[var.first], var.second);
        else
            full[var.first] = var.second;
    }
}

void dfsans(int start, int add, int muchii) { ///formam dist de la noduri la centroid
    if(muchii >= ans || add > k) ///deja e drum prea lung
        return;
    if(umap.find(add) != umap.end())
        umap[add] = min(umap[add], muchii);
    else
        umap[add] = muchii;
    for(const auto& x : v[start]) {
        if(x.nod == parent[start] || f[x.nod])
            continue;
        dfsans(x.nod, add + x.dist, muchii + 1);
    }
}

void build(int start) { ///de la subarborele lui start INCEPEM
    parent[start] = -1;
    dfssize(start);

    centroid = -1;
    dfscentroid(start, weight[start]);

    parent[centroid] = -1; ///rebuild in subarborele nostru sizeurile de parinti etc
    dfssize(centroid); ///reindexam parintii basically

    full.clear();
    for(const auto& x : v[centroid]) {
        if(f[x.nod])
            continue;
        umap.clear();
        dfsans(x.nod, x.dist, 1); ///formezi drumurile
        updateans(x.nod); ///unim fiul si si comparam
    }
    f[centroid] = 1;
    for(const auto& x : v[centroid]) { ///facem si in subarbori
        if(!f[x.nod])
            build(x.nod);
    }

}

int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
    n = N, k = K;
    v.resize(n + 1);
    for(int i = 0; i < n - 1; i++) {
        v[h[i][0]].push_back({h[i][1], l[i]});
        v[h[i][1]].push_back({h[i][0], l[i]});
    }
    build(0);
    if(ans == INF)
        ans = -1;
    return ans;
}

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