Submission #1316265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316265		turral	Race (IOI11_race)	C++20	0 / 100	0 ms	332 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

#define int long long
#define pi pair<int,int>

const int INF = 3e18;

// map -> length <-> min nºroads (ending  on our vertex i)
// int 1 -> we sum this num to all lengths (to let us use S2L)
// int 2 -> the same but to nºroads

int dfs_sz(int i, int p, vector<vector<pi> > & G, vector<int> & subTreeSz){
    int res=1;

    for (auto[j,w] : G[i]){
        if (j == p) continue;

        res += dfs_sz(j, i, G, subTreeSz);
    }

    return subTreeSz[i] = res;
}

void dfs(int i, int p, int & addLength, int & addRoads, int & res, unordered_map<int,int> & minRoads, vector<vector<pi> > & G, vector<int> & subTreeSz, int K){
    int mxSz=0, mxJ=-1, mxJW;
    for (auto [j, w] : G[i]){
        if (j != p && subTreeSz[j] > mxSz){
            mxSz = subTreeSz[j];
            mxJ = j;
            mxJW = w;
        }
    }

    if (mxJ == -1){
        minRoads[0] = 0;
        addLength = addRoads = 0;
        return;
    }

    dfs(mxJ, i, addLength, addRoads, res, minRoads, G, subTreeSz, K);
    addLength += mxJW;
    ++addRoads;

    for (auto [j, w] : G[i]){
        if (j == p || j == mxJ) continue;
        unordered_map<int, int> auxMinRoads;
        int auxAddL=0, auxAddR=0;
        dfs(j, i, auxAddL, auxAddR, res, auxMinRoads, G, subTreeSz, K);
        
        for (auto [l, cnt] : auxMinRoads){
            int nl = l+w+auxAddL-addLength;
            int ncnt = cnt+1+auxAddR-addRoads;

            if (!minRoads.count(nl)){
                minRoads[nl] = ncnt;
            } else {
                minRoads[nl] = min(minRoads[nl], ncnt);
            }
            
        }

        if (minRoads.count(K - addLength)){
            res = min(res, minRoads[K - addLength]+addRoads);
        }
    }

    if (minRoads.count(K - addLength)){
        res = min(res, minRoads[K - addLength]+addRoads);
    }
}

signed best_path(signed N, signed K, signed H[][2], signed L[]){
    vector<vector<pi> > G(N);
    for (int i=0; i<N-1; ++i){
        int u = H[i][0], v = H[i][1];
        int w = L[i];

        G[u].push_back(pi(v,w));
        G[v].push_back(pi(u,w));
    }

    vector<int> subTreeSz(N); 
    dfs_sz(0, -1, G, subTreeSz);

    unordered_map<int, int> minRoads;
    int addLength=0, addRoads=0;
    int res=INF;
    dfs(0, -1, addLength, addRoads, res, minRoads, G, subTreeSz, K);

    signed nres = (res>=INF ? -1 : res);
    return nres;
}

/*
signed main(){
    int N, K; cin >> N >> K;
    vector<vector<int> > H(N, vector<int>(2));
    vector<int> L(N);
    for (int i=0; i<N-1; ++i){
        cin >> H[i][0] >> H[i][1] >> L[i];
    }

    cout << best_path(N, K, H, L) << '\n';
    return 0;
}
*/

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