/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 5010;
const ll inf = 1e18;
int n, a[maxn], h[maxn];
ll c[maxn];
vector < int > adj[maxn];
void input()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i] >> h[i] >> c[i];
if (a[i] != i)
adj[a[i]].push_back(i);
}
}
unordered_map < int, int > tag;
void compress()
{
vector < int > values;
for (int i = 1; i <= n; i ++)
values.push_back(h[i]);
sort(values.begin(), values.end());
for (int i = 0; i < n; i ++)
tag[values[i]] = i + 1;
}
ll dp[maxn][maxn], temp[maxn];
int used[maxn];
set < pair < int, ll > > spot[maxn];
void add_to_set(int v, pair < int, ll > cur)
{
set < pair < int, ll > > :: iterator it = spot[v].lower_bound({v, -inf});
if (it != spot[v].end() && it -> first == cur.first)
{
cur.second += it -> second;
spot[v].erase(it);
}
spot[v].insert(cur);
}
void dfs(int v)
{
used[v] = 1;
for (int u : adj[v])
{
dfs(u);
for (int j = n; j >= 1; j --)
{
dp[v][j] += dp[u][j];
}
if (spot[u].size() > spot[v].size())
swap(spot[v], spot[u]);
for (pair < int, ll > cur : spot[u])
add_to_set(v, cur);
}
set < pair < int, ll > > :: iterator it;
ll sum = 0;
while(spot[v].size() > 0)
{
it = spot[v].lower_bound({tag[h[v]], inf});
if (it == spot[v].begin())
break;
it = prev(it);
if (sum + it -> second > c[v])
{
pair < int, ll > nw = *it;
nw.second -= (c[v] - sum);
sum = c[v];
spot[v].erase(it);
add_to_set(v, nw);
///spot[v].insert(nw);
break;
}
else
{
sum += it -> second;
spot[v].erase(it);
}
}
/**cout << "state " << v << " " << h[v] << endl;
for (int j = 1; j <= n; j ++)
cout << dp[v][j] << " ";
cout << endl;
for (pair < int, ll > cur : spot[v])
cout << cur.first << " " << cur.second << endl;
cout << "----------" << endl;*/
add_to_set(v, {1, sum});
add_to_set(v, {tag[h[v]] + 1, c[v]});
///add_to_set(v, {tag[h[v]] + 1, c[v] - sum});
//spot[v].insert({1, sum});
///spot[v].insert({tag[h[v]] + 1, c[v] - sum});
/**for (int j = 0; j <= n; j ++)
temp[j] = 0;
for (pair < int, ll > cur : spot[v])
for (int d = cur.first; d <= n; d ++)
temp[d] += cur.second;*/
for (int j = 1; j <= n; j ++)
{
if (j != tag[h[v]])
dp[v][j] += c[v];
}
for (int j = n - 1; j > 0; j --)
{
dp[v][j] = min(dp[v][j], dp[v][j + 1]);
}
/**for (int j = 1; j <= n; j ++)
{
if (temp[j] != dp[v][j])
{
cout << "Fuck " << v << endl;
for (int d = 1; d <= j + 10; d ++)
cout << temp[d] << " " << dp[v][d] << endl;
cout << "HERE " << tag[h[v]] << " " << j << " " << c[v] - sum << " " << sum << endl;
exit(0);
}
}
cout << "passed " << v << endl;*/
}
void calculate_states()
{
ll ans = 0;
for (int i = 1; i <= n; i ++)
{
if (used[i])
continue;
dfs(i);
ll s = 0;
for (pair < int, ll > cur : spot[i])
{
if (cur.first == 1)
s += cur.second;
}
ans += s;
}
cout << ans << endl;
}
void solve()
{
input();
compress();
calculate_states();
}
int main()
{
freopen("test.txt", "r", stdin);
solve();
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:194:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | freopen("test.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
