Submission #487237

#	Time	Username	Problem	Language	Result	Execution time	Memory
487237		aymanrs	경주 (Race) (IOI11_race)	C++14	43 / 100	3065 ms	72924 KiB

race

#include <bits/stdc++.h>
//#include "race.h"
 
#define ll      long long
#define pii     pair<ll, ll>
#define fi      first
#define se      second
#define pb      push_back
 
using namespace std;
 
const ll MX=200007, INF=1e9+7;
 
vector<pii> adj[MX];
map<ll, ll> ada[MX];
ll N, K, ret=INF;
void DFS(ll par, ll wpar, ll x){
    ada[x][0]=0;
    for(auto i:adj[x]){
        ll v=i.fi, w=i.se;
        if(v==par)
            continue;
        DFS(x, w, v);
        if(ada[x].size()<ada[v].size())
            swap(ada[x], ada[v]);
        for(auto j:ada[v]){
            ll tot=j.fi, sisa=K-tot;
            if(ada[x].count(sisa)){
                ret=min(ret, ada[x][sisa]+j.se);
            }
        }
        for(auto j:ada[v]){
            ll tot=j.fi;
            if(ada[x].count(tot)) ada[x][tot] = min(ada[x][tot], j.se);
            else ada[x][tot] = j.se;
        }
    }
    vector<pair<ll, ll>> tambah;
    for(auto i=ada[x].begin(); i!=ada[x].end(); i++){
        pair<ll, ll> tmp=*i;
 
            tmp.se++;
            if(tmp.fi+wpar<=K)
                tambah.pb({tmp.fi+wpar, tmp.se});
    }
    ada[x].clear();
    for(auto i:tambah)
        ada[x][i.fi]=i.se;
    ada[x][0]=0;
    if(ada[x].count(K))
        ret=min(ret, ada[x][K]);
}
 
int best_path(int n, int k, int H[][2], int L[]){
    N=n, K=k;
    for(ll i=0, u, v, w; i<N-1; i++){
        u=H[i][0], v=H[i][1], w=L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    DFS(0, 0, 0);
    return (ret>=INF?-1:ret);
}
// int main(){
//     //int H[][2] = {{0, 1},{0, 2},{2, 3},{3, 4},{4, 5},{0, 6},{6, 7},{6, 8},{8, 9},{8, 10}};
//     //int L[] = {3,4,5,4,6,3,2,5,6,7};
//     int H[][2] = {{0,1},{1,2}, {2,3}};
//     int L[] = {1, 0, 1};
//     cout << best_path(4, 3, H, L) << '\n';
// }

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