제출 #1310721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310721		hitsuuj	경주 (Race) (IOI11_race)	C++20	0 / 100	2 ms	1080 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std; 
#define pii pair<int,int> 
#define pb push_back
#define inf 1e9
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? 

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