Submission #1264492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264492		ema_nicole	Race (IOI11_race)	C++17	100 / 100	303 ms	57336 KiB

race

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

using namespace std;
const int NMAX = 2e5;
const int INF = 1e9;
using ll = long long;

struct muchii {
    int nod, cost;
};
vector <vector <muchii>> adj;
int n, k;

struct noduri{
    int parent = -1;

    int weight = 1; ///al subarborelui
    int lant;

    ll dist = 0; ///de la 0 la nod
    int depth = 0; ///basically CATE muchii de la 0 la nod
}v[NMAX + 2];

int cnt = 0; ///cate lanturi

void dfsbuild(int start) {
    bool ok = 0;
    for(auto x : adj[start]) {
        if(x.nod == v[start].parent)
            continue;
        ok = 1;
        v[x.nod].parent = start;
        v[x.nod].dist = v[start].dist + x.cost;
        v[x.nod].depth = v[start].depth + 1;
        dfsbuild(x.nod);
        v[start].weight += v[x.nod].weight;
    }
    ///formam lanturile
    if(!ok) { ///frunza, lant nou
        cnt++;
        v[start].lant = cnt;
        return;
    }
    int maxx = 0, chain = 0;
    for(auto x : adj[start]) {
        if(x.nod == v[start].parent)
            continue;
        if(v[x.nod].weight > maxx) {
            maxx = v[x.nod].weight;
            chain = v[x.nod].lant;
        }
    }
    v[start].lant = chain;
}

vector <map <ll, int>> umap; ///pt fiec lant
int ans = INF;
void solve(int start) {

    for(auto x : adj[start]) { ///prima oara fiul heavy
        if(x.nod != v[start].parent && v[x.nod].lant == v[start].lant) {
            solve(x.nod);
            break;
        }
    }
    for(auto x : adj[start]) {
        if(x.nod == v[start].parent || v[x.nod].lant == v[start].lant)
            continue;
        solve(x.nod);

        ///Small to large guys
        if(umap[v[start].lant].size() < umap[v[x.nod].lant].size())
            swap(umap[v[start].lant], umap[v[x.nod].lant]);

        ///Step 1) pt fiec fiu light, faci query cu lantul mare
        for(auto var : umap[v[x.nod].lant]) {
            ll caut = k + 2 * v[start].dist - var.first;
            if(umap[v[start].lant].find(caut) != umap[v[start].lant].end()) {
                ans = min(ans, var.second + umap[v[start].lant][caut] -
                                   2 * v[start].depth);
            }
        }

        ///Step 2) pt fiec fiu light, adaugi in map-ul lantului mare
        for(auto var : umap[v[x.nod].lant]) {
            if(umap[v[start].lant].find(var.first) != umap[v[start].lant].end())
                umap[v[start].lant][var.first] = min(umap[v[start].lant][var.first], var.second);
            else
                umap[v[start].lant][var.first] = var.second;
        }
        umap[v[x.nod].lant].clear();
    }
    ///query ca lantul poate se termina in el
    if(umap[v[start].lant].find(v[start].dist + k) != umap[v[start].lant].end())
        ans = min(ans, umap[v[start].lant][v[start].dist + k] - v[start].depth);

    ///la FINAL adaugam si nr nostru
    if(umap[v[start].lant].find(v[start].dist) != umap[v[start].lant].end())
        umap[v[start].lant][v[start].dist] = min(umap[v[start].lant][v[start].dist],
                                                 v[start].depth);
    else
        umap[v[start].lant][v[start].dist] = v[start].depth;
}


int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
    n = N, k = K;
    adj.resize(n + 1);
    for(int i = 0; i < n - 1; i++) {
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }
    dfsbuild(0);

    /*for(int i = 0; i < n; i++)
        cout << v[i].parent << "  " << v[i].weight << " " << v[i].lant << "  "
             << v[i].dist << " " << v[i].depth << '\n';*/

    umap.resize(cnt + 1);
    solve(0);

    if(ans == INF)
        ans = -1;
    return ans;
}

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