| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1310720 | hitsuuj | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define inf 1e18
const int lim=2e5;
vector<pii>g[lim+10];
vector<int>l(lim+10);
int ans=inf,n,k;
map<int,int> dfs(int u,int par){
map<int,int>cur;
for(auto [v,w]:g[u]){
if(v==par) continue;
cout<<u<<" "<<v<<' '<<w<<endl;
map<int,int> anak=dfs(v,u);
anak[w]=1;
// langsung kita tambahin weightnya itu kah?
if(anak.size()>cur.size()) swap(cur,anak);
// cek apakah ada yang match jadi k
for(auto [x,y]:anak){
if(x>k) continue;
int tar=k-x;
// cout<<"cek "<<u<<" "<<x<<" "<<y<<endl;
if(cur[tar]){
ans=min(ans,y+cur[tar]);
}
// dari anak berarti + 1 kah
if(cur[x]) cur[x+w]=min(cur[x+w],y+1);
else cur[x+w]=y+1;
}
}
return cur;
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N,k=K;
for(int i=0;i<n-1;i++){
g[H[i][0]].pb({H[i][1],L[i]});
g[H[i][1]].pb({H[i][0],L[i]});
}
dfs(1,-1);
return ans;
}
// finding secara global untuk s to l how
// pakain small to large krn nanti buat tiap distance bakalan di kirim ke atasnya dengan cepat with map
// subsoal
// (1&2) brute force aja tiap 2 kota
// (3) k=100 -> maximum 100 node kalau nggak consider yang 0 -> brute force cuman ada yang ada nodenya (yang 0 di skip)
// (4)
// 1. untuk suatu node arahnya cuman dua
// 2. pilih 2 dari semua branch yang ada?
#include "race.h"
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(2==scanf("%d %d",&N,&K));
for(i=0; i<N-1; i++)
my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = best_path(N,K,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}