Submission #1082091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082091		dwuy	Magic Tree (CEOI19_magictree)	C++14	3 / 100	93 ms	21072 KiB

magictree

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 2+100005;

struct Node{
    int lz, sum;
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n = 0){
        this->n = n;
        this->tree.assign(n<<2|3, {0, 0});
    }

    void down(int id){
        if(tree[id].lz == 0) return;
        tree[id<<1].lz = tree[id<<1|1].lz = 1;
        tree[id<<1].sum = tree[id<<1|1].sum = 0;
        tree[id].lz = 0;
    }

    void update(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        tree[id].sum = val;
        for(id>>=1; id; id>>=1) tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
    }

    void clear(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            tree[id].sum = 0;
            tree[id].lz = 1;
            return;
        }
        down(id);
        int mid = (l + r)>>1;
        clear(l, mid, id<<1, u, v);
        clear(mid + 1, r, id<<1|1, u, v);
        tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
    }

    void clear(int l, int r){
        clear(1, n, 1, l, r);
    }

    int get(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].sum;
        int mid = (l + r)>>1;
        return get(l, mid, id<<1, u, v) + get(mid + 1, r, id<<1|1, u, v);
    }

    int get(int l, int r){
        return get(1, n, 1, l, r);
    }
};

int n, m, k;
int dfsID = 0;  
int p[MX];
int h[MX];
int w[MX];
int num[MX];
int clo[MX];
vector<int> G[MX];
vector<int> T[MX];

void dfs(int u){
    h[u] = h[p[u]] + 1;
    num[u] = ++dfsID;
    for(int v: G[u]) dfs(v);
    clo[u] = dfsID;
}

int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n >> m >> k;
    for(int i=2; i<=n; i++){
        cin >> p[i];
        G[p[i]].push_back(i);
    }
    for(int i=1; i<=m; i++){
        int u, d;
        cin >> u >> d;
        T[d].push_back(u);
        cin >> w[u];
    }

    dfs(1);
    SMT smt(n);
    int ans = 0;
    for(int i=k; i>=1; i--) if(T[i].size()){
        sort(T[i].begin(), T[i].end(), [&](const int &a, const int &b) -> bool {return h[a] > h[b];});
        vector<int> vt;
        for(int u: T[i]){
            int cost = smt.get(num[u], clo[u]);
            if(w[u] > cost){
                ans += w[u] - cost;
                smt.clear(num[u], clo[u]);
                vt.push_back(u);
            }
            else smt.update(num[u], clo[u]);
        }
        for(int u: T[i]){
            smt.clear(num[u], num[u]);
        }
        for(int u: vt){
            smt.update(num[u], w[u]);
        }
    }
    cout << ans;

    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17