結果

問題 No.2439 Fragile Apple Tree
ユーザー kenken714kenken714
提出日時 2023-08-12 04:27:41
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,845 bytes
コンパイル時間 1,921 ms
コンパイル使用メモリ 165,748 KB
実行使用メモリ 73,688 KB
最終ジャッジ日時 2024-11-22 12:49:08
合計ジャッジ時間 40,207 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 458 ms
70,544 KB
testcase_01 AC 797 ms
31,936 KB
testcase_02 AC 782 ms
31,660 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 AC 787 ms
31,616 KB
testcase_06 AC 787 ms
31,724 KB
testcase_07 AC 741 ms
31,584 KB
testcase_08 AC 737 ms
31,616 KB
testcase_09 AC 7 ms
10,496 KB
testcase_10 AC 7 ms
10,240 KB
testcase_11 AC 6 ms
10,368 KB
testcase_12 AC 6 ms
10,496 KB
testcase_13 AC 6 ms
10,496 KB
testcase_14 AC 711 ms
30,464 KB
testcase_15 AC 700 ms
31,744 KB
testcase_16 AC 821 ms
31,832 KB
testcase_17 AC 801 ms
31,852 KB
testcase_18 AC 469 ms
29,184 KB
testcase_19 AC 319 ms
19,840 KB
testcase_20 AC 182 ms
17,792 KB
testcase_21 AC 47 ms
10,880 KB
testcase_22 AC 476 ms
21,888 KB
testcase_23 AC 214 ms
15,744 KB
testcase_24 AC 278 ms
18,944 KB
testcase_25 AC 352 ms
25,344 KB
testcase_26 AC 419 ms
27,904 KB
testcase_27 AC 282 ms
20,864 KB
testcase_28 AC 7 ms
10,496 KB
testcase_29 AC 6 ms
10,496 KB
testcase_30 AC 7 ms
10,496 KB
testcase_31 AC 609 ms
32,344 KB
testcase_32 AC 607 ms
73,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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