제출 #1222044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222044		elaksher	경주 (Race) (IOI11_race)	C++20	컴파일 에러	0 ms	0 KiB

race

/*-*-*-*-*-*-*-*-*-*-*-*-*
 *    while(noSuccess){   *
 *        try Again();    *
 *        if(dead)        *
 *           break;       *
 *    }                   *
 *-*-*-*-*-*-*-*-*-*-*-*-*/
 
#include <bits/stdc++.h>
// "إِنَّ اللَّهَ وَمَلَائِكَتَهُ يُصَلُّونَ عَلَى النَّبِيِّ ۚ يَا أَيُّهَا الَّذِينَ آمَنُوا صَلُّوا عَلَيْهِ وَسَلِّمُوا تَسْلِيمًا"
// You don't have to be great to start but you have to start to be great.
using namespace std;
#define int long long
#define ll long long
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
 
const int N = 2e5 + 5;
vector<pair<int, int>> g[N];
int sz[N], is_removed[N];
int k, ans = 1e10, n;
map<int, int> cnt;
int get_sz(int u, int p)
{
    sz[u] = 1;
    for (auto [v, _] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        sz[u] += get_sz(v, u);
    }
    return sz[u];
}
 
int get_cent(int u, int p, int cur_sz)
{
    for (auto [v, _] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        if (sz[v] * 2 > cur_sz)
            return get_cent(v, u, cur_sz);
    }
    return u;
}
void dfs(int v, int p, int depth, int delta, int w)
{
    if(cnt.count(w))    
        cnt[w] = min(cnt[w], depth);
    else cnt[w] = depth;
    for (auto [u, W] : g[v])
    {
        if (u == p || is_removed[u])
            continue;
        dfs(u, v, depth + 1, delta, w + W);
    }
}
void get_ans(int u, int p, int depth, int w)
{
    if (k - w >= 0 && cnt.count(k - w))
        ans = min(ans, cnt[k - w] + depth);
    for (auto [v, W] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        get_ans(v, u, depth + 1, W + w);
    }
}
 
void comp(int v)
{
    int size = get_sz(v, -1), cent = get_cent(v, -1, size);
    cnt[0] = 0;
    for (auto [u, w] : g[cent])
    {
        if (is_removed[u])
            continue;
        get_ans(u, cent, 1, w);
        dfs(u, cent, 1, 1, w);
    }
    cnt.clear();
    is_removed[cent] = 1;
    for (auto [u, _] : g[cent])
    {
        if (is_removed[u])
            continue;
        comp(u);
    }
}
 
// int32_t main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
//     cin >> n >> k;
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         g[u].push_back({v, w});
//         g[v].push_back({u, w});
//     }
//     comp(0);
//     cout << ans;
//     return 0;
// }

extern "C" {
    int best_path(int nn, int kk, int h[][2], int l[]) {
        n = nn; k = kk;
        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]});
        }
        comp(0);
        return ans == 1e10 ? -1 : ans;
    }
}

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

/usr/bin/ld: /tmp/ccfH9S1M.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