Submission #1105066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1105066	2024-10-25T09:09:33 Z	whoknow	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 200005
#define MAXK 1000005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const int INF = 1e9 + 7;
int n, K;
vector<ii>g[MAXN];
namespace sub1
{
int res = INF;
int sz[MAXN], h[MAXN];
ll s[MAXN];
bool del[MAXN];
vector<int>dp(MAXK);
vector<bool>dd(MAXK);
int cnt(int u, int p)
{
    sz[u] = 1;
    for(ii i : g[u])
    {
        int v = i.F;
        if(v == p || del[v])
            continue;
        sz[u] += cnt(v, u);
    }
    return sz[u];
}
int centroid(int u, int p, int cnt)
{
    for(ii i : g[u])
    {
        if(i.F == p || del[i.F])
            continue;
        if(sz[i.F] > cnt / 2)
            return centroid(i.F, u, cnt);
    }
    return u;
}
void dfs(int u, int p)
{
    h[u] = h[p] + 1;
    if(s[u]>K)
        return s[u]=0,void();
    if(K >= s[u])
        if(dp[K - s[u]] && dd[K - s[u]])
            res = min(res, dp[K - s[u]] + h[u]);
    for(ii i : g[u])
    {
        int v = i.F, w = i.S;
        if(v == p || del[v])
            continue;
        s[v] = s[u] + w;
        dfs(v, u);
    }
}
void clr(int u, int p)
{
    if(dd[s[u]])
        dp[s[u]] = min(dp[s[u]], h[u]);
    else
        dp[s[u]] = h[u];
    dd[s[u]] = 1;
    s[u] = 0, h[u] = 0;
    for(ii i : g[u])
    {
        int v = i.F;
        if(v == p || del[v])
            continue;
        clr(v, u);
    }
}
void build(int u, int p)
{
    int mid = centroid(u, 0, cnt(u, 0));
    dd[0] = 1;
    for(ii i : g[mid])
    {
        int v = i.F, w = i.S;
        if(del[v])
            continue;
        s[v] = s[mid] + w;
        dfs(v, mid);
        clr(v, mid);
    }
    vector<int>(MAXK).swap(dp);
    vector<bool>(MAXK).swap(dd);
    del[mid] = 1;
    for(ii i : g[mid])
    {
        int v = i.F;
        if(del[v])
            continue;
        build(v, mid);
    }
}
void solve()
{
    build(1, 0);
    cout << res;
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> K;
    for(int i = 1; i < n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x++, y++;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    sub1::solve();
}
/**
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
**/

Compilation message

race.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main()
      | ^~~~
/usr/bin/ld: /tmp/ccU2R3ua.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPGlDX7.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccPGlDX7.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