Submission #387995

#	Time	Username	Problem	Language	Result	Execution time	Memory
387995		BartolM	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	529 ms	109596 KiB

worst_reporter2

#define DEBUG 0
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;

const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int LOG=18;
const int OFF=(1<<18);

int n, uk=1;
int nx[N], val[N], cost[N], komp[N], koji[N], bio[N], in[N];
vector <int> lsr[N], ls[N];
vector <int> v, saz;
map <int, ll> M[N], dp[N];
ll zbr[N], suma=0;

void dfs1(int node) {
    if (bio[node]) return;
    bio[node]=1;
    dfs1(nx[node]);
    v.pb(node);
}

void dfs2(int node, int poc) {
    if (bio[node]==2) return;
    bio[node]=2;
    M[poc][val[node]]++;
    zbr[poc]+=cost[node];
    komp[node]=poc;

    #if DEBUG
        printf("komp: %d, node: %d, val: %d, cost: %d\n", poc, node, val[node], cost[node]);
    #endif // DEBUG

    for (int sus:lsr[node]) dfs2(sus, poc);
}

void rek(int node) {
    koji[node]=node;
    for (int sus:ls[node]) {
        rek(sus);
        if (dp[koji[node]].size()<dp[koji[sus]].size()) koji[node]=koji[sus];
    }
    for (int sus:ls[node]) {
        if (koji[sus]==koji[node]) continue;
        for (pil pp:dp[koji[sus]]) dp[koji[node]][pp.X]+=pp.Y;
    }
    if (!in[node]) return;
    dp[koji[node]][val[node]]+=cost[node];
    ll curr=cost[node], dod=0;

    while (1) {
        auto it=dp[koji[node]].upper_bound(val[node]);
        if (it==dp[koji[node]].end()) break;
        if (it->Y <= curr) curr-=it->Y, dod+=it->Y, dp[koji[node]].erase(it);
        else {
            it->Y+=dod-cost[node];
            break;
        }
    }

    #if DEBUG
        printf("node: %d: ", node);
        for (pil pp:dp[koji[node]]) {
            printf("(%d, %lld) ", pp.X, pp.Y);
        }
        printf("\n");
    #endif // DEBUG
}

void solve() {
    for (int i=1; i<=n; ++i) dfs1(i);
    reverse(v.begin(), v.end());
    for (int i:v) if (bio[i]==1) dfs2(i, i);
    for (int i=1; i<=n; ++i) {
        if (komp[nx[i]]!=komp[i]) {
            ls[komp[nx[i]]].pb(komp[i]);
            in[komp[i]]++;
        }
    }
    ll sol=0;
    for (int i=1; i<=n; ++i) {
        if (in[i] || komp[i]!=i) continue;
        ll res=0, curr=0;
        rek(i);
        auto it=dp[koji[i]].begin();
        for (pil pp:M[i]) {
            while (it!=dp[koji[i]].end() && it->X<=pp.X) curr+=it->Y, it++;
            res=max(res, curr+pp.Y);
        }
        while (it!=dp[koji[i]].end()) curr+=it->Y, it++;
        res=max(res, curr);
        sol+=res;
    }
    #if DEBUG
        printf("suma == %lld, sol: %lld\n", suma, sol);
    #endif // DEBUG
    printf("%lld\n", suma-sol);
}

void load() {
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        scanf("%d %d %d", &nx[i], &val[i], &cost[i]);
        lsr[nx[i]].pb(i);
        saz.pb(val[i]);
        suma+=cost[i];
    }
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    int m=saz.size();
    for (int i=1; i<=n; ++i) val[i]=m-(lower_bound(saz.begin(), saz.end(), val[i])-saz.begin());
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void load()':
worst_reporter2.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |         scanf("%d %d %d", &nx[i], &val[i], &cost[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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