Submission #717279

#	Time	Username	Problem	Language	Result	Execution time	Memory
717279		vjudge1	Race (IOI11_race)	C++17	0 / 100	6 ms	8916 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 nn, int kk, int h[][2], int l[])
{
    curK = kk;
    for(int i=0; i<nn-1; i++)
    {
        adj[h[i][0]+1].pb({h[i][1]+1, l[i]});
        adj[h[i][1]+1].pb({h[i][0]+1, 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<=nn; i++)
        adj[i].clear();

    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:122:17: warning: iteration 1000005 invokes undefined behavior [-Waggressive-loop-optimizations]
  122 |         best[d] = OO;
      |         ~~~~~~~~^~~~
race.cpp:121:19: note: within this loop
  121 |     for(int d=0; d<=K; d++)
      |                  ~^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57