Submission #1131906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131906		t9unkubj	Race (IOI11_race)	C++20	100 / 100	505 ms	45800 KiB

race

#include "race.h"
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
int brute(int n,int k,vc<int>u,vc<int>v,vc<int>L){
    vvc<pair<int,int>>g(n);
    rep(i,n-1){
        g[u[i]].push_back({v[i],L[i]});
        g[v[i]].push_back({u[i],L[i]});
    }
    int ans=1e9;
    rep(i,n){
        auto dfs=[&](auto&dfs,int u,int v,ll d,int t)->void{
            if(d&&d==k)chmin(ans,t);
            for(auto&[x,L]:g[u]){
                if(x==v)continue;
                dfs(dfs,x,u,d+L,t+1);
            }
        };
        dfs(dfs,i,-1,0,0);
    }
    if(ans>n)return -1;
    return ans;
}
int solve(int n,int k,vc<int>u,vc<int>v,vc<int>L){
    rep(i,n-1){
        if(L[i]==k)return 1;
    }
    vvc<pair<int,int>>g(n);
    rep(i,n-1){
        g[u[i]].push_back({v[i],L[i]});
        g[v[i]].push_back({u[i],L[i]});
    }
    vc<int>sz(n);
    vc<int>done(n);
    auto center=[&](int x){
        vc<int>vs;
        auto dfs=[&](auto&dfs,int u,int v)->void{
            sz[u]=1;
            vs.push_back(u);
            for(auto&[x,L]:g[u]){
                if(done[x])continue;
                if(x==v)continue;
                dfs(dfs,x,u);
                sz[u]+=sz[x];
            }
        };
        dfs(dfs,x,-1);
        pair<int,int>res{(int)1e9,-1};
        for(auto&x:vs){
            if(sz[x]*2>=vs.size()){
                chmin(res,pair<int,int>{sz[x],x});
            }
        }
        assert(res.second!=-1);
        return res.second;
    };  
    int ans=1e9;
    auto rec=[&](auto&rec,int now)->void{
        unordered_map<ll,int>dp;
        int C=center(now);
        dp[0]=0;
        auto DFS=[&](auto&DFS,int u,int v,ll D,int de,vc<pair<ll,ll>>&upd)->void{
            
            upd.push_back({D,de});
            for(auto&[x,L]:g[u]){
                if(done[x])continue;
                if(x==v)continue;
                DFS(DFS,x,u,D+L,de+1,upd);
            }
        };  
        for(auto&[x,L]:g[C]){
            if(!done[x]){
                vc<pair<ll,ll>>upd;
                DFS(DFS,x,C,L,1,upd);
                for(auto&[x,y]:upd){
                    if(dp.count(k-x)){
                        chmin(ans,dp[k-x]+y);
                    }
                }
                for(auto&[x,y]:upd){
                    if(!dp.count(x)||dp[x]>y){
                        dp[x]=y;
                    }
                }
            }
        }
        done[C]=1;
        for(auto&[x,L]:g[C]){
            if(!done[x]){
                rec(rec,x);
            }
        }
    };
    rec(rec,0);
    if(ans>n)return -1;
    return ans;
}

int best_path(int N, int K, int H[][2], int L[])
{   
    vc<int>u(N-1),v(N-1);
    vc<int>l(N-1);
    rep(i,N-1)u[i]=H[i][0],v[i]=H[i][1];
    rep(i,N-1)l[i]=L[i];
    return solve(N,K,u,v,l);
}

namespace judge{
    void ch(){
        while(1){
            int n=4;
            vc<int>u(n-1),v(n-1);
            rep(i,n-1)u[i]=i;
            rep(i,n-1)v[i]=i+1;
            vc<int>l(n-1);
            rep(i,n-1)l[i]=rand()%10;
            int k=rand()%10+1;
            if(solve(n,k,u,v,l)!=brute(n,k,u,v,l)){
                dbg(n,k,u,v,l);
                dbg(solve(n,k,u,v,l));
                dbg(brute(n,k,u,v,l));
                assert(0);
            }
        }
    }
    void run(){
        int n,k;
        cin>>n>>k;
        vc<int>u(n-1),v(n-1);
        rep(i,n-1)cin>>u[i]>>v[i];
        vc<int>l(n-1);
        rep(i,n-1)cin>>l[i];
        dbg(solve(n,k,u,v,l));
    }
};
//int main(){judge::ch();}
//g++ race/race.cpp -D t9unkubj
/*
4 9
0 1
1 2
2 3
2 
7
7



4 3
0 1
1 2
1 3
1 2 4

3 3
0 1
1 2
1 1

11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3
4
5
4
6
3
2
5
6
7

*/

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