Submission #387999

#TimeUsernameProblemLanguageResultExecution timeMemory
387999BartolMWorst Reporter 4 (JOI21_worst_reporter4)C++17
100 / 100
579 ms135396 KiB
#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 (stderr)

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]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...