結果

問題 No.417 チューリップバブル
ユーザー sntea
提出日時 2016-08-31 06:32:55
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 5,165 bytes
コンパイル時間 2,813 ms
コンパイル使用メモリ 190,636 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 12:44:18
合計ジャッジ時間 8,773 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef LOCAL111
#else
    #define NDEBUG
#endif
#include <bits/stdc++.h>
const long long INF = 1e12;
using namespace std;
#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RBP(i,a) for(auto& i : a)
#ifdef LOCAL111
    #define DEBUG(x) cout<<#x<<": "<<(x)<<endl
    template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
    #define DEBUG(x) true
    template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
#define rangej(a,b,c) ((a) <= (c) and (c) < (b))
#define rrangej(b,c) rangej(0,b,c)
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
typedef pair<LL,LL> LP;
void ios_init(){
    //cout.setf(ios::fixed);
    //cout.precision(12);
#ifdef LOCAL111
    return;
#endif
    ios::sync_with_stdio(false); cin.tie(0);    
}
//library
typedef long long cost_t;
class Edge {
public:
    int to;
    cost_t cost;
    
    Edge(){
    }
    Edge(int x,cost_t y){
        to = x;
        cost = y;
    }
    bool operator< (const Edge& x) const {
        return cost < x.cost;
    }
    bool operator> (const Edge& x) const {
        return cost > x.cost;
    }
};
class Graph {
private:
    //const long long int INF = (long long)1e18;
    vector<vector<Edge> > v; 
    int n;
public:
    Graph(int x){
        n = x;
        v = vector<vector<Edge> >(x);
    }
    vector<Edge>& operator[](int x){
        return v[x];
    }
    const vector<Edge>& operator[](int x) const {
        return v[x];
    }
    int size() const {
        return n;
    }
    void add_edge(int from, Edge e){
        v[from].push_back(e);
    }
    void add_edge(int from, int to, cost_t cost){
        add_edge(from,Edge(to,cost));
    }
};
vector<cost_t> dijkstra(int from, const Graph& v) {
    vector<cost_t> dist(v.size(),INF);
    priority_queue<Edge,vector<Edge>,greater<Edge>> que;
    que.push(Edge(from,0));
    while(!que.empty()){
        Edge e = que.top();
        que.pop();
        if(dist[e.to] == INF){
            dist[e.to] = e.cost;
            for(auto to : v[e.to]){
                if(dist[to.to] == INF)
                    que.push(Edge(to.to, e.cost+to.cost));
            }
        }
    }
    return dist;
}
vector<cost_t> bellmanford(int from, const Graph& g){
    vector<cost_t> res(g.size(),INF);
    res[from] = 0;
    bool conf = true;
    int cnt = 0;
    while(conf){
        conf = false;
        for(int i = 0; i < g.size(); i++){
            if(res[i] != INF)
            for(const auto& e : g[i]){
                if(res[e.to] > res[i]+e.cost){
                    conf = true;
                    res[e.to] = res[i]+e.cost;
                }
            }
        }
        if(cnt > g.size()+5) return vector<cost_t>();
        cnt++;
    }
    return res;
}
Graph prim(const Graph g){
    using T = tuple<cost_t, int, int>;
    priority_queue<T, vector<T>, greater<T>> qu;
    int n = g.size();
    assert(n != 0);
    vector<bool> added(n,false);
    qu.emplace(0,0,0);
    Graph res(n);
    while(!qu.empty()){
        int from, to;
        cost_t cost;
        tie(cost, from, to) = qu.top();
        qu.pop();
        if(!added[to]){
            added[to] = true;
            res.add_edge(from, to, cost);
            res.add_edge(to, from, cost);
            for(const auto &e : g[to]){
                if(!added[e.to]){
                    qu.emplace(e.cost, to, e.to);
                }
            }
        }
    }
    return res;
}
vector<int> tree_getorder(const Graph &g, int root){
    vector<int> res;
    function<void(int p, int pre)> func = [&](int p, int pre){
        for(auto &e : g[p]){
            if(e.to != pre){
                func(e.to,p);
            }
        }
        res.push_back(p);
    };
    func(root,-1);
    return res;
}
vector<int> tree_getpar(const Graph &g, int root){
    vector<int> par(g.size(),root);
    function<void(int p, int pre)> func = [&](int p, int pre){
        par[p] = pre;
        for(auto &e : g[p]){
            if(e.to != pre){
                func(e.to,p);
            }
        }
    };
    func(root,root);
    return par;
}
//liblary
// int dfs(const vector<vector<int>> &memo, const Graph &g, int p, int pre, int time){
//  int res = INF;
//  if(memo[p][time] != -1) return res;
//  vector<P> vv;
//  RBP(e,g[p]){
//      if(e.to != pre){
//          dfs(memo,g,e.to,p,time);
//      }
//  }
// }
int main()
{
    ios_init();
    int n,m;
    cin >> n >> m;
    vector<int> u(n);
    REP(i,n) cin >> u[i];
    Graph g(n);
    REP(i,n-1){
        int a,b,c;
        cin >> a >> b >> c;
        g.add_edge(a,b,c);
        g.add_edge(b,a,c);
    }
    vector<vector<LL>> dp(n,vector<LL>(m+1,-INF));
    // dpite(ALL(tree_getorder(g,0)));
    auto topo = tree_getorder(g,0);
    auto par = tree_getpar(g,0);
    dpite(ALL(par));
    REP(i,SZ(topo)){
        int p = topo[i];
        dp[p][0] = u[p];
        RBP(e,g[p]) if(e.to != par[p]){
            vector<LL> tmp = dp[p];
            RFOR(j,0,m+1){
                FOR(k,j+2*e.cost,m+1){
                    tmp[k] = max(tmp[k],
                     dp[p][k-(j+2*e.cost)]+dp[e.to][j]);
                }
            }
            if(p == 4){
                DEBUG(e.to);
                dpite(ALL(dp[p])); dpite(ALL(tmp));
            }
            dp[p] = tmp;
        }
    }
    DEBUG(endl);
    REP(i,n) dpite(ALL(dp[i]));
    cout << *max_element(ALL(dp[0])) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0