oj.uz

Submission #387999

# Submission time Handle Problem Language Result Execution time Memory
387999 2021-04-09T17:09:04 Z BartolM Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 579 ms 135396 KB 
#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]]+=cost[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;

    assert(M[node].size()==1);

    dp[koji[node]][val[node]]+=cost[node];
    auto it=dp[koji[node]].upper_bound(val[node]);
    if (it!=dp[koji[node]].end()) it->Y-=cost[node];
    while (it!=dp[koji[node]].end() && it->Y<=0) {
        auto slj=it; slj++;
        if (slj!=dp[koji[node]].end()) slj->Y+=it->Y;
        dp[koji[node]].erase(it);
        it=slj;
    }

    #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++;

            #if DEBUG
                printf("i: %d, (%d, %lld), curr: %lld\n", i, pp.X, pp.Y, curr);
            #endif // DEBUG

            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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28528 KB Output is correct
2 Correct 16 ms 28524 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 23 ms 30144 KB Output is correct
6 Correct 22 ms 29656 KB Output is correct
7 Correct 23 ms 29424 KB Output is correct
8 Correct 24 ms 30112 KB Output is correct
9 Correct 22 ms 29692 KB Output is correct
10 Correct 21 ms 29476 KB Output is correct
11 Correct 21 ms 29380 KB Output is correct
12 Correct 21 ms 30008 KB Output is correct
13 Correct 21 ms 29884 KB Output is correct
14 Correct 21 ms 29580 KB Output is correct
15 Correct 21 ms 29644 KB Output is correct
16 Correct 25 ms 30540 KB Output is correct
17 Correct 22 ms 29860 KB Output is correct
18 Correct 19 ms 29332 KB Output is correct
19 Correct 22 ms 29872 KB Output is correct
20 Correct 22 ms 29644 KB Output is correct
21 Correct 20 ms 29584 KB Output is correct
22 Correct 21 ms 29760 KB Output is correct
23 Correct 23 ms 29428 KB Output is correct
24 Correct 22 ms 29892 KB Output is correct
25 Correct 20 ms 29692 KB Output is correct
26 Correct 21 ms 29980 KB Output is correct
27 Correct 22 ms 29772 KB Output is correct
28 Correct 22 ms 29984 KB Output is correct
29 Correct 21 ms 30028 KB Output is correct
30 Correct 22 ms 30156 KB Output is correct
31 Correct 22 ms 30028 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30156 KB Output is correct
2 Correct 537 ms 109656 KB Output is correct
3 Correct 423 ms 85044 KB Output is correct
4 Correct 542 ms 106672 KB Output is correct
5 Correct 456 ms 85080 KB Output is correct
6 Correct 295 ms 66476 KB Output is correct
7 Correct 304 ms 62388 KB Output is correct
8 Correct 255 ms 87268 KB Output is correct
9 Correct 219 ms 87128 KB Output is correct
10 Correct 179 ms 87096 KB Output is correct
11 Correct 248 ms 74784 KB Output is correct
12 Correct 214 ms 74704 KB Output is correct
13 Correct 446 ms 135396 KB Output is correct
14 Correct 355 ms 99736 KB Output is correct
15 Correct 163 ms 62092 KB Output is correct
16 Correct 370 ms 81592 KB Output is correct
17 Correct 210 ms 74692 KB Output is correct
18 Correct 160 ms 74556 KB Output is correct
19 Correct 341 ms 76140 KB Output is correct
20 Correct 174 ms 63660 KB Output is correct
21 Correct 338 ms 82792 KB Output is correct
22 Correct 197 ms 75440 KB Output is correct
23 Correct 185 ms 87088 KB Output is correct
24 Correct 357 ms 84180 KB Output is correct
25 Correct 281 ms 90664 KB Output is correct
26 Correct 282 ms 94044 KB Output is correct
27 Correct 286 ms 93364 KB Output is correct
28 Correct 295 ms 93364 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28528 KB Output is correct
2 Correct 16 ms 28524 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 23 ms 30144 KB Output is correct
6 Correct 22 ms 29656 KB Output is correct
7 Correct 23 ms 29424 KB Output is correct
8 Correct 24 ms 30112 KB Output is correct
9 Correct 22 ms 29692 KB Output is correct
10 Correct 21 ms 29476 KB Output is correct
11 Correct 21 ms 29380 KB Output is correct
12 Correct 21 ms 30008 KB Output is correct
13 Correct 21 ms 29884 KB Output is correct
14 Correct 21 ms 29580 KB Output is correct
15 Correct 21 ms 29644 KB Output is correct
16 Correct 25 ms 30540 KB Output is correct
17 Correct 22 ms 29860 KB Output is correct
18 Correct 19 ms 29332 KB Output is correct
19 Correct 22 ms 29872 KB Output is correct
20 Correct 22 ms 29644 KB Output is correct
21 Correct 20 ms 29584 KB Output is correct
22 Correct 21 ms 29760 KB Output is correct
23 Correct 23 ms 29428 KB Output is correct
24 Correct 22 ms 29892 KB Output is correct
25 Correct 20 ms 29692 KB Output is correct
26 Correct 21 ms 29980 KB Output is correct
27 Correct 22 ms 29772 KB Output is correct
28 Correct 22 ms 29984 KB Output is correct
29 Correct 21 ms 30028 KB Output is correct
30 Correct 22 ms 30156 KB Output is correct
31 Correct 22 ms 30028 KB Output is correct
32 Correct 24 ms 30156 KB Output is correct
33 Correct 537 ms 109656 KB Output is correct
34 Correct 423 ms 85044 KB Output is correct
35 Correct 542 ms 106672 KB Output is correct
36 Correct 456 ms 85080 KB Output is correct
37 Correct 295 ms 66476 KB Output is correct
38 Correct 304 ms 62388 KB Output is correct
39 Correct 255 ms 87268 KB Output is correct
40 Correct 219 ms 87128 KB Output is correct
41 Correct 179 ms 87096 KB Output is correct
42 Correct 248 ms 74784 KB Output is correct
43 Correct 214 ms 74704 KB Output is correct
44 Correct 446 ms 135396 KB Output is correct
45 Correct 355 ms 99736 KB Output is correct
46 Correct 163 ms 62092 KB Output is correct
47 Correct 370 ms 81592 KB Output is correct
48 Correct 210 ms 74692 KB Output is correct
49 Correct 160 ms 74556 KB Output is correct
50 Correct 341 ms 76140 KB Output is correct
51 Correct 174 ms 63660 KB Output is correct
52 Correct 338 ms 82792 KB Output is correct
53 Correct 197 ms 75440 KB Output is correct
54 Correct 185 ms 87088 KB Output is correct
55 Correct 357 ms 84180 KB Output is correct
56 Correct 281 ms 90664 KB Output is correct
57 Correct 282 ms 94044 KB Output is correct
58 Correct 286 ms 93364 KB Output is correct
59 Correct 295 ms 93364 KB Output is correct
60 Correct 16 ms 28492 KB Output is correct
61 Correct 16 ms 28492 KB Output is correct
62 Correct 16 ms 28520 KB Output is correct
63 Correct 16 ms 28492 KB Output is correct
64 Correct 579 ms 95300 KB Output is correct
65 Correct 463 ms 83776 KB Output is correct
66 Correct 566 ms 99716 KB Output is correct
67 Correct 481 ms 83652 KB Output is correct
68 Correct 410 ms 70528 KB Output is correct
69 Correct 351 ms 67124 KB Output is correct
70 Correct 423 ms 66540 KB Output is correct
71 Correct 242 ms 51888 KB Output is correct
72 Correct 496 ms 70376 KB Output is correct
73 Correct 245 ms 58004 KB Output is correct
74 Correct 410 ms 77084 KB Output is correct
75 Correct 261 ms 64584 KB Output is correct
76 Correct 219 ms 64468 KB Output is correct
77 Correct 384 ms 77392 KB Output is correct
78 Correct 221 ms 64924 KB Output is correct
79 Correct 502 ms 92552 KB Output is correct
80 Correct 362 ms 75576 KB Output is correct
81 Correct 305 ms 66316 KB Output is correct
82 Correct 329 ms 70592 KB Output is correct
83 Correct 185 ms 60228 KB Output is correct
84 Correct 426 ms 76136 KB Output is correct
85 Correct 463 ms 76148 KB Output is correct
86 Correct 443 ms 72888 KB Output is correct
87 Correct 441 ms 76124 KB Output is correct
88 Correct 434 ms 76044 KB Output is correct