結果

問題 No.2439 Fragile Apple Tree
ユーザー kenken714kenken714
提出日時 2023-08-12 04:21:44
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,754 bytes
コンパイル時間 1,656 ms
コンパイル使用メモリ 160,740 KB
実行使用メモリ 82,240 KB
最終ジャッジ日時 2024-11-22 12:48:27
合計ジャッジ時間 39,329 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 464 ms
78,720 KB
testcase_01 AC 758 ms
31,872 KB
testcase_02 AC 751 ms
31,616 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 AC 759 ms
31,744 KB
testcase_06 AC 775 ms
31,872 KB
testcase_07 AC 715 ms
31,488 KB
testcase_08 AC 731 ms
31,488 KB
testcase_09 AC 8 ms
10,624 KB
testcase_10 AC 7 ms
10,240 KB
testcase_11 AC 7 ms
10,368 KB
testcase_12 AC 6 ms
10,496 KB
testcase_13 AC 7 ms
10,368 KB
testcase_14 AC 684 ms
30,464 KB
testcase_15 AC 655 ms
31,872 KB
testcase_16 AC 756 ms
31,872 KB
testcase_17 AC 757 ms
31,872 KB
testcase_18 AC 435 ms
29,056 KB
testcase_19 AC 296 ms
19,584 KB
testcase_20 AC 164 ms
17,920 KB
testcase_21 AC 47 ms
10,624 KB
testcase_22 AC 456 ms
21,888 KB
testcase_23 AC 205 ms
15,872 KB
testcase_24 AC 274 ms
18,816 KB
testcase_25 AC 329 ms
25,344 KB
testcase_26 AC 388 ms
27,904 KB
testcase_27 AC 262 ms
20,992 KB
testcase_28 AC 7 ms
10,368 KB
testcase_29 AC 7 ms
10,496 KB
testcase_30 AC 7 ms
10,368 KB
testcase_31 AC 597 ms
32,344 KB
testcase_32 AC 599 ms
82,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007

vector<int> g[300010];
int ans;
int sz[300010], par[300010], a[300010], b[300010];
ll c[300010], cv[300010], co[300010];

void dfs(int v, int p){
    sz[v] = 1;
    for(auto nv : g[v]){
        if(nv == p)continue;
        dfs(nv, v);
        sz[v] += sz[nv];
        par[nv] = v;
    }
}
int main(){
    ll N, Q;
    cin >> N >> Q;
    REP(i, N - 1){
        cin >> a[i] >> b[i];
        a[i]--;b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
        cin >> cv[i];
    }
    ans = N;
    dfs(0, -1);
    REP(i, N - 1){
        if(par[a[i]] == b[i])co[a[i]] = c[a[i]] = cv[i];
        else co[b[i]] = c[b[i]] = cv[i];
    }
    REP(i, Q){
        ll t;
        cin >> t;
        if(t == 1){
            ll v, x;
            cin >> v >> x;
            v--;
            int nowv = v;
            while(nowv != 0){
                c[nowv] -= x;
                if(c[nowv] <= 0){
                    ans -= sz[nowv];

                    int nev = par[nowv];
                    while(nev != 0){
                        sz[nev] -= sz[nowv];
                        c[nev] += co[nowv] - (c[nowv] + x);
                        nev = par[nev];
                    }
                    break;
                }
                nowv = par[nowv];
            }
        }
        else{
            cout << ans << endl;
        }
    }
}
0