oj.uz

Submission #964926

# Submission time Handle Problem Language Result Execution time Memory
964926 2024-04-17T17:59:55 Z Younis_Dwai Race (IOI11_race) C++14
0 / 100
 17 ms 35164 KB 
#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std ;
const int MN=1e6+1;
bitset<MN> vis;
int res,k;
vector<int> dp(MN),sz(MN);
vector<pair<int,int>> adj[MN];
void dfs_sz(int node , int par){
     sz[node]=1;
     for(auto u : adj[node]){
         if(vis[u.F] || u.F==par) continue ;
         dfs_sz(u.F,node);
     }
     return ;
}
int  get_centroid(int node ,int par , int d){
     for(auto u : adj[node]){
         if(vis[u.F] || u.F==par || sz[u.F]<=d) continue ;
         return get_centroid(u.F,node,d);
     }
     return node;
}
void dfs_calc(int node, int par , int done ,int dis){
     res=min(res,dp[k-dis]+done);
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_calc(u.F,node,done+1,dis+u.S);
     }
     return ;
}
void dfs_upd(int node , int par , int done , int dis){
     dp[dis]=min(done,dp[dis]);
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_upd(u.F,node,done+1,dis+u.S);
     }
     return ;
}
void dfs_fill(int node , int par ,int dis){
     dp[dis]=1e9;
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_fill(u.F,node,dis+u.S);
     }
     return ;
}
void dfs(int node){
     dfs_sz(node,node);
     int centroid=get_centroid(node,node,sz[node]/2);
     vis[centroid]=1;
     dp[0]=0;
     for(auto u : adj[centroid]){
         if(vis[u.F] || u.S>k) continue ;
         dfs_calc(u.F,centroid,1,u.S);
         dfs_upd(u.F,centroid,1,u.S);
     }
     for(auto u : adj[centroid]){
         if(u.S>k || vis[u.F]) continue ;
         dfs_fill(u.F,centroid,u.S);
     }
     for(auto u :  adj[centroid]){
         if(vis[u.F]) continue ;
         dfs(u.F);
     }
     return ;
}
int best_path(int N, int K, int H[][2], int L[]){
    res=1e9;
    k=K;
    for(int i=0;i<=K;i++) dp[i]=1e9;
    for(int i=0;i<N-1;i++){
        //adj[H[i][0]].pb({H[i][1],L[i]});
        //adj[H[i][1]].pb({H[i][0],L[i]});
    }
    dfs(0);
    if(res==1e9) return -1;
    else return res;
    return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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