제출 #1083602

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

race

#include <bits/stdc++.h>
//#include "race.h"
#define task "road"
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

using namespace std;

const int N = 2e5 + 5;

ll n, k, ans = 1e9;
vector<pii> vt[N];
ll in[N], out[N], pos[N], sz[N], up[N][22];
pair<ll, int> h[N];
int cnt = 0;

void dfs(int u, int p)
{
    in[u] = ++cnt;
    pos[cnt] = u;
    sz[u] = 1;
    for(auto v : vt[u])
    {
        if(v.fi == p)
            continue;
        h[v.fi].fi = h[u].fi + v.se;
        h[v.fi].se = h[u].se + 1;
        up[v.fi][0] = u;
        for(int i = 1; i <= 20; i++)
            up[v.fi][i] = up[up[v.fi][i - 1]][i - 1];
        dfs(v.fi, u);
        sz[u] += sz[v.fi];
    }
    out[u] = cnt;
}

int lca(int u, int v)
{
    if(h[u].se != h[v].se)
    {
        if(h[u].se < h[v].se)
            swap(u, v);
        int tmp = h[u].se - h[v].se;
        for(int i = 0; i <= 20; i++)
            if((tmp >> i) & 1)
                u = up[u][i];
    }
    if(u == v)
        return u;
    for(int i = 20; i >= 0; i--)
        if(up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

map<ll, pii> mp;

void add(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
    {
        pii tmp = mp[h[pos[i]].fi];
        if(tmp.fi == 0 || tmp.fi > h[pos[i]].se)
            mp[h[pos[i]].fi] = {h[pos[i]].se, pos[i]};
    }
}

void del(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
        mp[h[pos[i]].fi] = {0, 0};
}

void solve(int u, int p)
{
    pair<int, int> big = {0, -1};
    for(auto v : vt[u])
        if(v.fi != p)
            big = max(big, {sz[v.fi], v.fi});
    for(auto v : vt[u])
    {
        if(v.fi == big.se || v.fi == p)
            continue;
        solve(v.fi, u);
        del(v.fi);
    }
    if(big.se != -1)
        solve(big.se, u);
    for(auto v : vt[u])
        if(v.fi != big.se && v.fi != p)
            add(v.fi);
    mp[h[u].fi] = {h[u].se, u};
    for(auto j : vt[u])
    {
        if(j.fi != big.se && j.fi != p)
            for(int i = in[j.fi]; i <= out[j.fi]; i++)
            {
                int v = pos[i];
                ll tmp = h[u].fi + k - (h[v].fi - h[u].fi);
                pii huhu = mp[tmp];
                if(huhu.fi == 0)
                    continue;
                int haha = huhu.se;
                if(lca(haha, v) == u)
                    ans = min(ans, huhu.fi - h[u].se + h[v].se - h[u].se);
//                if(ans == 4)
//                    cout << u << " " << v << " " << haha << '\n';
            }
    }
    pii huhu = mp[h[u].fi + k];
    if(huhu.fi == 0)
        return;
    ans = min(ans, huhu.fi - h[u].se);
    return;
}

//int best_path(int m, int g, int h[][2], int l[])
int best_path()
{
//    n = m;
//    k = g;
//    for(int i = 0; i < n - 1; i++)
//    {
//        vt[h[i][0]].push_back({h[i][1], l[i]});
//        vt[h[i][1]].push_back({h[i][0], l[i]});
//    }
//    dfs(0, -1);
    solve(0, -1);
    if(ans == (int) 1e9)
        return -1;
    return ans;
}

//int main()
//{
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL), cout.tie(NULL);
//    cin >> n >> k;
//    for(int i = 1; i < n; i++)
//    {
//        int x, y, w;
//        cin >> x >> y >> w;
//        vt[x].push_back({y, w});
//        vt[y].push_back({x, w});
//    }
//    dfs(0, -1);
//    cout << best_path();
//    return 0;
//}

/*
4 3
0 1 1
1 2 2
1 3 4
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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

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