Submission #717271

#	Time	Username	Problem	Language	Result	Execution time	Memory
717271		vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define MP make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define vvi vector<vector<int>>
#define loop(i,a,b) for(int i = a; i <= b; i++)
#define FOR(i, a, b) for(int i = a; i < b; i++)

#define _ ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
const int OO = 1e9;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
//best depth available for current weight
int curK, sz[N], best[K];
bool rem[N];
vector<pair<int,int>> adj[N];

void preSz(int u, int par)
{
    sz[u] = 1;
    for(auto e:adj[u])
    {
        if(e.F == par || rem[e.F])
            continue;
        preSz(e.F, u);
        sz[u] += sz[e.F];
    }
}

int getCen(int u, int par, int subSz)
{
    int mxSz = subSz - sz[u];
    int ret = -1;
    for(auto e:adj[u])
    {
        if(e.F == par || rem[e.F])
            continue;

        ret = max(ret, getCen(e.F, u, subSz));
        mxSz = max(mxSz, sz[e.F]);
    }
    if(mxSz <= subSz / 2)
        ret = u;
    return ret;
}

void update(int u, int par, int curD, int curW, bool add)
{
    if(curW > curK)
        return;
    if(add)
        best[curW] = min(best[curW], curD);
    else
        best[curW] = OO;
    for(auto e:adj[u])
    {
        if(e.F == par || rem[e.F])
            continue;
        update(e.F, u, curD+1, curW + e.S, add);
    }
}

int solve(int u, int par, int curD, int curW)
{
    if(curW > curK)
        return OO;
    int ans = curD + best[curK - curW];
    for(auto e:adj[u])
    {
        if(e.F == par || rem[e.F])
            continue;
        ans = min(ans, solve(e.F, u, curD+1, curW+e.S));
    }
    return ans;
}

int solveCen(int cen)
{
    int ans = OO;
    for(auto e:adj[cen])
    {
        if(rem[e.F])
            continue;
        update(e.F, cen, 1, e.S, true);
        ans = min(ans, solve(e.F,cen,1,e.S));
    }
    return ans;
}

int decompose(int node)
{
    preSz(node, 0);
    int cen = getCen(node, 0, sz[node]);
    int curAns = solveCen(cen);
    update(cen, 0, 0, 0,false);
    rem[cen] = true;
    for(auto e:adj[node])
    {
        if(rem[e.F])
            continue;
        curAns = min(curAns, decompose(e.F));
    }
    return curAns;
}


int best_path(int n, int k, int h[][2], int l[])
{
    curK = k;
    for(int i=0; i<n-1; i++)
    {
        ++h[i][0]; ++h[i][1];
        adj[h[i][0]].pb({h[i][1], l[i]});
        adj[h[i][1]].pb({h[i][0], l[i]});
    }
    for(int d=0; d<=k; d++)
        best[d] = OO;

    int ans = decompose(1);
    if(ans >= OO)
        ans = -1;
    for(int i=1; i<=n; i++)
        adj[i].clear();

    return ans;
}

void answerTC()
{
    int n, k;
    cin >> n >> k;
    int H[n-1][2];
    int L[n-1];

    for(int i=0; i<n-1; i++)
        cin >> H[i][0] >> H[i][1];

    for(int i=0; i<n-1; i++)
        cin >> L[i];

    cout << best_path(n, k, H, L);
}

int main() { _
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#endif

    int t = 1;
//    cin >> t;

    while(t--){
        answerTC();
    }

}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:152:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 | freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:152:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 | freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
      |                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc0tOsbE.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc70D4ME.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status