Submission #760278

#	Time	Username	Problem	Language	Result	Execution time	Memory
760278		MilosMilutinovic	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	11 ms	19156 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int n, a[N], h[N], c[N], deg[N], id[N], dep[N], mx[N];
bool was[N];
vector<int> grp[N];
int find_id(int i) {
    if (id[i] != -1) return id[i];
    id[i] = find_id(a[i]);
    dep[i] = dep[a[i]] + 1;
    return id[i];
}
vector<int> g[N];
void add_edge(int x, int y) {
    g[x].push_back(y);
    g[y].push_back(x);
}
int who[N];
ll dp[N];
multiset<pair<int, ll>> st[N];
int gfa(int x) { return who[x] == x ? x : who[x] = gfa(who[x]); }
void unite(int x, int y) {
    x = gfa(x);
    y = gfa(y);
    if (st[x].size() < st[y].size())
        swap(x, y);
    for (auto& p : st[y]) {
        st[x].insert(p);
    }
    st[y].clear();
    who[y] = x;
}
void dfs(int x, int fa) {
    dp[x] = c[x];
    who[x] = x;
    for (int y : g[x]) {
        if (y == fa) continue;
        dfs(y, x);
        unite(x, y);
    }
    while (!st[who[x]].empty()) {
        auto p = *prev(st[who[x]].end());
        if (p.first >= h[x]) {
            dp[x] += p.second;
            st[who[x]].erase(prev(st[who[x]].end()));
        } else break;
    }
    st[who[x]].emplace(h[x], dp[x]);
}
const int inf = 0x3f3f3f3f;
const int M = 100 * N;
int root[N], ls[M], rs[M], tsz;
ll sum[M];
void modify(int& v, int l, int r, int ql, int qr, ll x) {
    if (l > r || l > qr || r < ql) return;
    if (!v) v = ++tsz;
    if (ql <= l && r <= qr) { sum[v] += x; return; }
    int mid = l + r >> 1;
    modify(ls[v], l, mid, ql, qr, x);
    modify(rs[v], mid + 1, r, ql, qr, x);
}
ll query(int v, int l, int r, int p) {
    if (l == r) return sum[v];
    int mid = l + r >> 1;
    if (p <= mid)
        return query(ls[v], l, mid, p) + sum[v];
    else
        return query(rs[v], mid + 1, r, p) + sum[v];
}
ll solve(vector<int> ver, int g_id) {
    vector<int> cyc, tree;
    for (int x : ver) {
        if (dep[x] == 0)
            cyc.push_back(x);
        else
            tree.push_back(x);
    }
    for (int x : tree) {
        if (dep[a[x]] != 0)
            add_edge(x, a[x]);
    }
    for (int x : tree) {
        if (dep[x] == 1) {
            dfs(x, x);
            int prv = 0;
            for (auto& p : st[who[x]]) {
                modify(root[g_id], 0, inf, prv, p.first, p.second);
                prv = p.first + 1;
            }
        }
    }
    vector<int> vals;
    ll tot_sum = 0;
    for (int x : ver)
        vals.push_back(h[x]), tot_sum += c[x];
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    map<int, ll> mp;
    for (int x : cyc)
        mp[h[x]] += c[x];
    ll ans = 0;
    for (int v : vals) {
        ans = max(ans, mp[v] + query(root[g_id], 0, inf, v));
    }
    return tot_sum - ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &a[i], &h[i], &c[i]);
    }
    for (int i = 1; i <= n; i++) {
        deg[a[i]] += 1;
    }
    vector<int> que;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            que.push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        int x = que[i];
        deg[a[x]] -= 1;
        if (deg[a[x]] == 0) {
            que.push_back(a[x]);
        }
    }
    que.clear();
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0)
            que.push_back(i);
    for (int i = 1; i <= n; i++)
        id[i] = -1, dep[i] = 0;
    vector<vector<int>> cycs;
    for (int x : que) {
        if (!was[x]) {
            vector<int> cyc;
            int i = x;
            while (!was[i]) {
                was[i] = true;
                id[i] = cycs.size();
                cyc.push_back(i);
                i = a[i];
            }
            cycs.push_back(cyc);
        }
    }
    for (int i = 1; i <= n; i++) {
        id[i] = find_id(i);
        grp[id[i]].push_back(i);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (grp[i].empty()) continue;
        ans += solve(grp[i], i);
    }
    printf("%lld\n", ans);
}

/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

14

5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1

0

*/

Compilation message (stderr)

worst_reporter2.cpp: In function 'void modify(int&, int, int, int, int, long long int)':
worst_reporter2.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = l + r >> 1;
      |               ~~^~~
worst_reporter2.cpp: In function 'long long int query(int, int, int, int)':
worst_reporter2.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = l + r >> 1;
      |               ~~^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d%d%d", &a[i], &h[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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