Submission #674959

#	Time	Username	Problem	Language	Result	Execution time	Memory
674959		skittles1412	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	809 ms	131532 KiB

worst_reporter2

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxn = 2e5 + 5;

struct DS {
    struct Node {
        long v, lazy;
        int lc, rc;
    };

    inline static int heap_ptr = 1;
    inline static Node heap[1 << 25] {};

    static int alloc() {
        return heap_ptr++;
    }
    static void alloc(int& o) {
        if (!o) {
            o = alloc();
        }
    }

    static void maintain(int o) {
        auto& [v, lazy, lc, rc] = heap[o];
        v = min(heap[lc].v, heap[rc].v) + lazy;
    }

    static void merge(int& a, int& b, int l, int r) {
        if (!b) {
            return;
        } else if (!a) {
            a = b;
            return;
        }
        auto& [v, lazy, lc, rc] = heap[a];
        int mid = (l + r) / 2;
        lazy += heap[b].lazy;
        merge(lc, heap[b].lc, l, mid);
        merge(rc, heap[b].rc, mid + 1, r);
        maintain(a);
    }

    friend void merge(DS& a, DS& b) {
        merge(a.root, b.root, 0, maxn);
    }

    static long get(int o, int l, int r, int ind) {
        if (!o) {
            return 0;
        }
        auto& [v, lazy, lc, rc] = heap[o];
        if (l == r) {
            return v;
        }
        int mid = (l + r) / 2;
        if (ind <= mid) {
            return lazy + get(lc, l, mid, ind);
        } else {
            return lazy + get(rc, mid + 1, r, ind);
        }
    }

    static void upd_add(int& o, long x) {
        alloc(o);
        heap[o].lazy += x;
        maintain(o);
    }

    static long query_min(int o, int l, int r, int ql, int qr) {
        if (!o) {
            return 0;
        }
        auto& [v, lazy, lc, rc] = heap[o];
        if (ql <= l && r <= qr) {
            return v;
        }
        int mid = (l + r) / 2;
        long ans = 1e18;
        if (ql <= mid) {
            ans = min(ans, query_min(lc, l, mid, ql, qr));
        }
        if (mid < qr) {
            ans = min(ans, query_min(rc, mid + 1, r, ql, qr));
        }
        return ans + lazy;
    }

    static void upd_set(int& o, int l, int r, int ql, int qr, long x) {
        alloc(o);
        auto& [v, lazy, lc, rc] = heap[o];
        if (ql <= l && r <= qr) {
            lc = rc = 0;
            v = lazy = x;
            return;
        }
        int mid = (l + r) / 2;
        x -= lazy;
        if (ql <= mid) {
            upd_set(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            upd_set(rc, mid + 1, r, ql, qr, x);
        }
        maintain(o);
    }

    int root = 0;

    long get(int ind) const {
        return get(root, 0, maxn, ind);
    }

    void upd_add(long x) {
        upd_add(root, x);
    }

    long query_min(int l, int r) const {
        return query_min(root, 0, maxn, l, r);
    }

    void upd_set(int l, int r, long x) {
        upd_set(root, 0, maxn, l, r, x);
    }

    void upd_min(int qr, long x) {
        int l = 0, r = qr + 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (query_min(mid, qr) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l <= qr) {
            upd_set(l, qr, x);
        }
    }
};

bool vis[maxn], in_cyc[maxn];
int arr[maxn], cost[maxn];
vector<int> graph[maxn];

DS dp(int u, int p = -1) {
    vis[u] = true;
    DS cur;
    for (auto& v : graph[u]) {
        if (v == p || in_cyc[v]) {
            continue;
        }
        auto&& ndp = dp(v, u);
        merge(cur, ndp);
    }
    long cans = cur.get(arr[u]);
    cur.upd_add(cost[u]);
    if (p != -1) {
        cur.upd_min(arr[u], cans);
    }
    return cur;
}

void solve() {
    int n;
    cin >> n;
    int par[n];
    for (int i = 0; i < n; i++) {
        cin >> par[i] >> arr[i] >> cost[i];
        par[i]--;
    }
    for (int i = 0; i < n; i++) {
        graph[par[i]].push_back(i);
    }
    vector<int> comp(arr, arr + n);
    sort(begin(comp), end(comp));
    comp.erase(unique(begin(comp), end(comp)), comp.end());
    for (int i = 0; i < n; i++) {
        arr[i] =
            int(lower_bound(begin(comp), end(comp), arr[i]) - comp.begin());
    }
    long ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i]) {
            continue;
        }
        int u = i;
        vector<int> st;
        do {
            vis[u] = true;
            st.push_back(u);
            u = par[u];
        } while (!vis[u]);
        vector<int> cyc(find(begin(st), end(st), u), st.end());
        DS cds;
        map<int, long> ccost;
        for (auto& a : cyc) {
            dbg(a);
            ccost[arr[a]] += cost[a];
            in_cyc[a] = true;
            auto&& xans = dp(a);
            merge(cds, xans);
        }
        long cans = cds.get(0);
        for (auto& [k, v] : ccost) {
            cans = min(cans, cds.get(k) - v);
        }
        dbg(i, cans);
        ans += cans;
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21