Submission #914697

#	Time	Username	Problem	Language	Result	Execution time	Memory
914697		asdasdqwer	Race (IOI11_race)	C++14	100 / 100	428 ms	97620 KiB

race

// solution using small-to-large merging
#include <bits/stdc++.h>
using namespace std;
#include "race.h"

#define pii array<int,2>

int best_path(int N, int K, int H[][2], int L[]) {
    vector<vector<pii>> g(N);
    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]});
        if (L[i] == K) return 1;
    }

    vector<vector<pii>> child(N);
    function<void(int,int)> ch=[&](int node, int pv) {
        for (auto [x, w]:g[node]) {
            if (x == pv)continue;
            child[node].push_back({x, w});
            ch(x, node);
        }
    };

    ch(0, -1);

    // maps for merging: key is the length of the path and 
    // value is the minimum number of edges needed for this length
    vector<map<int,int>> sm(N);

    // candidate answer for each node
    vector<int> cand(N, 1e7);

    // value that has to be added to all weights of subtree
    vector<int> upd(N, 0);

    // value that has to be added to all path lenghts
    vector<int> len(N, 0);

    function<void(int)> dfs=[&](int node) {
        if (child[node].size() == 0) {
            return;
        }

        int mxSize=-1, mxChild=-1, mxW = 0;
        for (auto [x, w]:child[node]) {
            dfs(x);
            if ((int)sm[x].size() > mxSize) {
                mxSize = sm[x].size();
                mxChild = x;
                mxW = w;
            }
        }

        if (mxSize == 0) {
            for (auto [x, w]:child[node]) {
                if (sm[node].find(K - w) != sm[node].end()) {
                    cand[node] = min(cand[node], 2);
                    // cout<<"found a path of length 2 at node "<<node<<"\n";
                }

                sm[node][w] = 1;
            }
            return;
        }

        // check for edge to max-size subtree only
        if (sm[mxChild].find(K - upd[mxChild] - mxW) != sm[mxChild].end()) {
            cand[node] = min(cand[node], sm[mxChild][K - upd[mxChild] - mxW] + len[mxChild] + 1);
            // cout<<"found a path of length "<<sm[mxChild][K - upd[mxChild] - mxW] + len[mxChild] + 1<<" at node "<<node<<"\n";
        }

        upd[node] = upd[mxChild] + mxW;
        len[node] = len[mxChild] + 1;
        sm[node].swap(sm[mxChild]);
        sm[node][mxW - upd[node]] = 1 - len[node];

        for (auto [x, w] : child[node]) {
            if (x==mxChild) continue;
            
            // go though all children values and update if found
            for (auto [gg,hh] : sm[x]) {
                int weight = gg + upd[x] + w;
                int numEdges = hh + 1 + len[x];
                if (sm[node].find(K - weight - upd[node]) != sm[node].end()) {
                    int val = sm[node][K - weight - upd[node]] + len[node];
                    cand[node] = min(cand[node], val + numEdges);
                    // cout<<"found a path of length "<<val + numEdges<<" at node "<<node<<"\n";
                }
            }

            // update if path with down edge only exists
            if (sm[node].find(K - w - upd[node]) != sm[node].end()) {
                cand[node] = min(cand[node], sm[node][K - w - upd[node]] + len[node] + 1);
                // cout<<"found a path of length "<<sm[node][K - w - upd[node]] + len[node] + 1<<" at node "<<node<<"\n";
            }

            // insert all children values
            for (auto [gg,hh] : sm[x]) {
                int weight = gg + upd[x] + w - upd[node];
                int numEdges = hh + 1 + len[x] - len[node];
                if (sm[node].find(weight) != sm[node].end()) {
                    sm[node][weight] = min(sm[node][weight], numEdges);
                }

                else {
                    sm[node][weight] = numEdges;
                }
            }

            // insert down edge only
            sm[node][w - upd[node]] = 1 - len[node];

        }
    };

    dfs(0);
    int mn = 1e7;
    for (int i=0;i<N;i++) {
        mn = min(mn, cand[i]);
    }

    if (mn == (int)1e7) {
        return -1;
    }

    return mn;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:18:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |         for (auto [x, w]:g[node]) {
      |                   ^
race.cpp: In lambda function:
race.cpp:46:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         for (auto [x, w]:child[node]) {
      |                   ^
race.cpp:56:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |             for (auto [x, w]:child[node]) {
      |                       ^
race.cpp:78:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         for (auto [x, w] : child[node]) {
      |                   ^
race.cpp:82:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |             for (auto [gg,hh] : sm[x]) {
      |                       ^
race.cpp:99:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |             for (auto [gg,hh] : sm[x]) {
      |                       ^

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