oj.uz

Submission #975962

# Submission time Handle Problem Language Result Execution time Memory
975962 2024-05-06T04:03:40 Z Amaarsaa Race (IOI11_race) C++14
0 / 100
 2 ms 12636 KB 
//#include "race.h"

#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
//#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=2e5+11;
const int lim=1e6+11;
int n, k, sz[N], vit[N], dp[lim], mx;
vector<int> ned;
int ans=-1;
vector<pii> adj[N];
int subtree(int u, int pa)
{
    sz[u] = 1;
    for (auto v: adj[u])
    {
        if (v.fi != pa && !vit[v.fi])
        {
            sz[u] += subtree(v.fi, u);
        }
    }
    return sz[u];
}
int cen(int u, int pa, int n)
{
    for (auto v: adj[u])
    {
        if (v.fi != pa && !vit[v.fi] && sz[v.fi] > n/2)
        {
            return cen(v.fi, u, n);
        }
    }
    return u;
}
void dfs(int u, int pa, int dis, int h, int ch)
{
    if(dis > k) return;
    if(ch)
    {
        if(dp[dis]==-1) dp[dis]=h;
        else dp[dis]=min(dp[dis], h);
        ned.push_back(dis);
    }
    else
    {
        if(dp[k-dis]!=-1)
        {
            if(ans==-1) ans=dp[k-dis]+h;
            else ans=min(ans, dp[k-dis]+h);
        }
    }
    for(auto v: adj[u])
    {
        if(v.fi != pa && !vit[v.fi]) dfs(v.fi, u, dis+v.sc, h+1, ch);
    }
}
void calc(int u)
{
    subtree(u, 0);
    int c = cen(u, 0, sz[u]);
    vit[c] = 1;
    for(auto u: adj[c])
    {
        if (!vit[u.fi])
        {
            dfs(u.fi, c, u.sc, 1, 0);
            dfs(u.fi, c, u.sc, 1, 1);
        }
    }
    for(int x : ned) dp[x]=-1;
    ned.clear();
    for(auto v: adj[c])
    {
        if (!vit[v.fi])
        {
            calc(v.fi);
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    for(int i=0, u, v, x; i+ 1<N; i++)
    {
    	u = H[i][0];
    	v = H[i][1];
    	x = L[i];
        adj[u+1].push_back({v+1, x});
        adj[v+1].push_back({u+1, x});
    }
    memset(dp, -1, sizeof dp);
    dp[0]=0;
    calc(1);
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -