제출 #1316249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316249		turral	Race (IOI11_race)	C++20	컴파일 에러	0 ms	0 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);
    }
}

int best_path(int N, int K, vector<vector<int> > H, vector<int> 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);

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

/*
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;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

race.cpp:11:17: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   11 | const int INF = 3e18;
      |                 ^~~~
/usr/bin/ld: /tmp/ccbOzMxi.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status