Submission #760326

#	Time	Username	Problem	Language	Result	Execution time	Memory
760326		MilosMilutinovic	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	13 ms	20024 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[gfa(x)].empty()) {
        auto p = *prev(st[gfa(x)].end());
        if (p.first >= h[x]) {
            dp[x] += p.second;
            st[gfa(x)].erase(prev(st[gfa(x)].end()));
        } else break;
    }
    st[gfa(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 (!v) return 0ll;
    if (l == r) { assert(l == p); 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);
            vector<pair<int, ll>> vec;
            for (auto& p : st[gfa(x)])
                vec.push_back(p);
//            for (int i = vec.size() - 2; i >= 0; i--) {
//                assert(vec[i].second >= vec[i + 1].second);
//          }
            vector<pair<int, ll>> new_vec;
            for (auto& p : vec) {
                while (new_vec.size() > 0 && new_vec.back().second <= p.second)
                    new_vec.pop_back();
                new_vec.push_back(p);
            }
            int prv = 0;
            for (auto& p : new_vec) {
                if (prv <= p.first) {
                    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 < que.size(); 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

20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771

2711043927

20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030

4012295156
*/

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:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i = 0; i < que.size(); i++) {
      |                     ~~^~~~~~~~~~~~
worst_reporter2.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d%d%d", &a[i], &h[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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