Submission #585994

#	Time	Username	Problem	Language	Result	Execution time	Memory
585994		krit3379	Race (IOI11_race)	C++17	100 / 100	1160 ms	37340 KiB

race

#include<bits/stdc++.h>
#include"race.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 200005

int cnt[N],k,ans=1e9;
bitset<N> dead;
vector<pair<int,int>> g[N];

class CT{
public:
    void dfs_sz(int s,int f){
        cnt[s]=1;
        for(auto [x,w]:g[s]){
            if(x==f||dead[x])continue;
            dfs_sz(x,s);
            cnt[s]+=cnt[x];
        }
    }
    int dfs_cen(int s,int f,int n){
        for(auto [x,w]:g[s]){
            if(x==f||dead[x])continue;
            if(cnt[x]>=n)return dfs_cen(x,s,n);
        }
        return s;
    }
    void sol(int s,int f,int sum,int cnt,map<int,int> &now){
        if(sum>k)return ;
        if(now.count(sum))now[sum]=min(now[sum],cnt);
        else now[sum]=cnt;
        for(auto [x,w]:g[s]){
            if(x==f||dead[x])continue;
            sol(x,s,sum+w,cnt+1,now);
        }
    }
    void find_root(int s){
        dfs_sz(s,0);
        int c=dfs_cen(s,0,cnt[s]/2);
        dead[c]=true;
        map<int,int> mp;
        for(auto [x,w]:g[c]){
            if(dead[x])continue;
            map<int,int> now;
            sol(x,c,w,1,now);
            for(auto [a,b]:now)if(mp.count(k-a))ans=min(ans,mp[k-a]+b);
            for(auto [a,b]:now){
                if(mp.count(a))mp[a]=min(mp[a],b);
                else mp[a]=b;
            }
        }
        if(mp.count(k))ans=min(ans,mp[k]);
        mp.clear();
        for(auto [x,w]:g[c])if(!dead[x])find_root(x);
    }
    void init(){
        find_root(1);
    }
}t;

int best_path(int n, int K,int h[N][2],int l[N]){
    for(int i=0;i<n-1;i++){
        int a=h[i][0],b=h[i][1];
        a++,b++;
        g[a].push_back({b,l[i]});
        g[b].push_back({a,l[i]});
    }
    k=K;
    t.init();
    return ans!=1e9?ans:-1;
}

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