Submission #1248454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248454		QuocSensei	경주 (Race) (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

#define ll long long
#define el cout << '\n'
#define ii pair<ll, ll>
#define fi first
#define se second

using namespace std;

const int maxn = 2e5;
const int maxk = 1e6;
const int INF = 1e9;

int n, k, sz[maxn + 10], mn[maxn + 10], ans = INF;
bool del[maxn + 10];
vector<ii> adj[maxn + 10];

void cnt_sz(int top, int p = -1)
{
    sz[top] = 1;
    for (ii pr : adj[top])
    {
        int next_top = pr.fi;
        if (next_top == p || del[next_top])
            continue;
        cnt_sz(next_top, top);
        sz[top] += sz[next_top];
    }
}
int find_centroid(int top, int tree_sz, int p = -1)
{
    for (ii pr : adj[top])
    {
        int next_top = pr.fi;
        if (next_top == p || del[next_top])
            continue;
        if (2 * sz[next_top] > tree_sz)
            return find_centroid(next_top, tree_sz, top);
    }
    return top;
}
void update_subtree(int top, int p = -1, int dist = 0, int cnte = 0, bool is_add = 0)
{
    if (dist <= k)
        if (is_add)
            mn[dist] = min(mn[dist], cnte);
        else
            mn[dist] = INF;
    for (ii pr : adj[top])
    {
        int next_top = pr.fi;
        int w = pr.se;
        if (next_top == p || del[next_top])
            continue;
        update_subtree(next_top, top, dist + w, cnte + 1, is_add);
    }
}
void get_subtree(int top, int p = -1, int dist = 0, int cnte = 0)
{
    if (dist <= k)
        ans = min(ans, cnte + mn[k - dist]);
    for (ii pr : adj[top])
    {
        int next_top = pr.fi;
        int w = pr.se;
        if (next_top == p || del[next_top])
            continue;
        get_subtree(next_top, top, dist + w, cnte + 1);
    }
}
void centroid_decomposition(int top)
{
    cnt_sz(top);
    int centroid = find_centroid(top, sz[top]);
    del[centroid] = 1;

    mn[0] = 0;
    for (ii pr : adj[centroid])
    {
        int next_top = pr.fi;
        int w = pr.se;
        if (del[next_top])
            continue;
        get_subtree(next_top, centroid, w, 1);
        update_subtree(next_top, centroid, w, 1, 1);
    }
    update_subtree(centroid, -1, 0, 0, 0);
    for (ii pr : adj[centroid])
    {
        int next_top = pr.fi;
        if (del[next_top])
            continue;
        centroid_decomposition(next_top);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("RACE.INP", "r"))
    {
        freopen("RACE.INP", "r", stdin);
        freopen("RACE.OUT", "w", stdout);
    }

    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        x++;
        y++;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    for (int i = 0; i <= k; i++)
        mn[i] = INF;
    centroid_decomposition(1);
    cout << (ans == INF ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("RACE.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("RACE.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc3dF6xG.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRpHzwo.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc3dF6xG.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