Submission #797503

#	Time	Username	Problem	Language	Result	Execution time	Memory
797503		Khizri	Race (IOI11_race)	C++17	21 / 100	1018 ms	262144 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,k,ans,par[mxn],sz;
ll sum[mxn];
vector<pii>vt[mxn];
vector<int>dis[mxn];
void dfs1(int u,int p,int dep,int cnt){
    if(dep==k) ans=min(ans,cnt);
    for(pii v:vt[u]){
        if(p!=v.F){
            dfs1(v.F,u,dep+v.S,cnt+1);
        }
    }
}
void dfs(int u,int p){
    //cout<<u<<' '<<p<<endl;
    par[u]=p;
    int node=p;
    int cnt=1;
    while(node!=-1&&sum[u]-sum[node]<=k){
        dis[node][sum[u]-sum[node]]=min(dis[node][sum[u]-sum[node]],cnt);
        cnt++;
        node=par[node];
        //cout<<node<<endl;
    }
    multiset<int>st[k+2];
    st[0].insert(0);
    for(int i=1;i<=k;i++) st[i].insert(1e9);
    for(pii pp:vt[u]){
        int v=pp.F,len=pp.S;
        if(v==p) continue;
        sum[v]=sum[u]+len;
        dfs(v,u);
        if(vt[u].size()<sz){
            for(int i=0;i<=k;i++){
                int dif=len+i;
                if(dif<=k){
                    st[dif].insert(dis[v][i]+1);
                    if(st[dif].size()>2){
                        st[dif].erase(--st[dif].end());
                    }
                }
            }
        }
    }
    if(vt[u].size()>sz) return;
    for(pii pp:vt[u]){
        int v=pp.F,len=pp.S;
        if(v==p) continue;
        for(int i=0;i<=k;i++){
            int dif=len+i;
            if(dif<=k&&st[dif].count(dis[v][i]+1)){
                st[dif].erase(st[dif].find(dis[v][i]+1));
            }
        }
        for(int i=0;i<=k;i++){
            int dif=len+i;
            if(dif<=k){
                int res=dis[v][i]+1;
                res+=*st[k-dif].begin();
                ans=min(ans,res);
            }
        }
        for(int i=0;i<=k;i++){
            int dif=len+i;
            if(dif<=k){
                st[dif].insert(dis[v][i]+1);
                if(st[dif].size()>2){
                    st[dif].erase(--st[dif].end());
                }
            }
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for(int i=0;i<n-1;i++){
        int u=H[i][0]+1,v=H[i][1]+1;
        vt[u].pb({v,L[i]});
        vt[v].pb({u,L[i]});
        if(L[i]==k) return 1;
    }
    if(n<=1000){
        ans=1e9;
        for(int i=1;i<=n;i++){
            dfs1(i,-1,0,0);
        }
        if(ans==1e9) return -1;
        return ans;
    }
    for(int i=1;i<=n;i++){
        dis[i].pb(0);
        for(int j=1;j<=k;j++){
            dis[i].pb(1e9);
        }
    }
    sz=sqrt(n);
    ans=1e9;
    dfs(1,-1);
    for(int i=1;i<=n;i++){
        if(vt[i].size()>sz){
            dfs1(i,-1,0,0);
        }
    }
    if(ans==1e9) return -1;
    return ans;
}
/*
g++ race.cpp grader.cpp ; .\a.exe
4 3 
0 1 1 
1 2 2 
1 3 4

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

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:47:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if(vt[u].size()<sz){
      |            ~~~~~~~~~~~~^~~
race.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     if(vt[u].size()>sz) return;
      |        ~~~~~~~~~~~~^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:115:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |         if(vt[i].size()>sz){
      |            ~~~~~~~~~~~~^~~

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