Submission #953402

#	Time	Username	Problem	Language	Result	Execution time	Memory
953402		efishel	Race (IOI11_race)	C++17	100 / 100	318 ms	57868 KiB

race

#include <bits/stdc++.h>
// #include "race.h"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ii = pair<int,int>; using ll = long long; using ull = unsigned long long;
using vi = vector<ll>;
void valid(int in){cout<<((in)?"YES\n":"NO\n");return;}
const int N = 1e6 + 7;
vector<ii> graph[N];
bool vis[N];int ans = 1e9, sz[N], mn[N],k;
void find_sz(int nodo ,int  p = -1){sz[nodo]=1;
    for(auto [v, cost] : graph[nodo]){if(v==p || vis[v])continue;
        find_sz(v,nodo);
        sz[nodo] += sz[v];
    }
}
int find_cent(int nodo, int raiz, int p = -1){
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        if(sz[v]>sz[raiz]/2)return find_cent(v, raiz, nodo);
    }return nodo;
}
void dfs_calc(int nodo, int sum = 0,int nivel = 0, int p = -1){
    if(sum>k)return;
    ans = min(ans, mn[k-sum]+ nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_calc(v, sum + cost, nivel+1, nodo);
    }
}
void dfs_add(int nodo, int sum = 0,  int nivel = 0, int p = -1){
    if(sum>k)return;
    mn[sum] = min(mn[sum],nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_add(v, sum+cost, nivel+1, nodo);
    }
}
void dfs_del(int nodo, int sum = 0, int nivel = 0, int p = -1){
    if(sum>k)return;
    mn[sum] =1e9;
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_del(v, sum+cost, nivel+1, nodo);
    }
}
void solve(int nodo){
    find_sz(nodo);int cen = find_cent(nodo,nodo);mn[0]=0;
    // fo(i,k+2) cout << mn[i] << " "; cout << endl;
    vis[cen]=1;
    for(auto [v,cost] : graph[cen]){
        if (vis[v]) continue;
        dfs_calc(v, cost, 1,cen);
        dfs_add(v,cost, 1,cen);
    }
    dfs_del(cen);
    for(auto [v,cost] : graph[cen]) if (!vis[v]) solve(v);
}
int best_path(int n, int K, int H[][2], int L[]){k=K;fill(mn, mn+k+3, 1e9);
    fo(i,n-1){
        graph[H[i][0]].pb({H[i][1], L[i]});
        graph[H[i][1]].pb({H[i][0], L[i]});
    }solve(0);return (ans == 1e9 ? -1 : ans);
}

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