//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int par[MAXN], w[MAXN], deg[MAXN];
vi adj[MAXN];
ll dp[MAXN], pre[MAXN], depth[MAXN];
ll diam(int u) {
ll mx1 = 0, mx2 = 0;
for (int v: adj[u]) {
if (mx1 < depth[v] + w[v]) {
mx2 = mx1;
mx1 = depth[v] + w[v];
} else if (mx2 < depth[v] + w[v])
mx2 = depth[v] + w[v];
}
return mx1 + mx2;
}
int main() {
int n;
ni(n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &par[i], &w[i]);
deg[par[i]]++;
adj[par[i]].pb(i);
}
deque<int> pq;
for (int i = 1; i <= n; i++)
if (deg[i] == 0)
pq.pb(i);
while (!pq.empty()) {
int u = pq.front(); pq.pop_front();
dp[u] = max(dp[u], diam(u));
dp[par[u]] = max(dp[par[u]], dp[u]);
depth[par[u]] = max(depth[par[u]], depth[u] + w[u]);
if (--deg[par[u]] == 0)
pq.pb(par[u]);
par[u] = 0;
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (par[i] == 0)
continue;
ll sm = 0, m1 = -INF, m2 = -INF, cur = 0;
vll act;
act.pb(mp(0, 0));
int u = i;
while (par[u] != 0) {
cur = max(cur, max(dp[u], diam(u)));
act.pb(mp(depth[u], w[u]));
sm += w[u];
int nx = u;
u = par[u];
par[nx] = 0;
}
for (int i = 1; i < act.size(); i++)
pre[i] = pre[i - 1] + act[i].se;
for (int i = 1; i < act.size(); i++) {
cur = max(cur, act[i].fi + max(pre[i - 1] + m1, sm - pre[i - 1] + m2));
m1 = max(m1, act[i].fi - pre[i - 1]);
m2 = max(m2, act[i].fi + pre[i - 1]);
}
ans += cur;
}
prl(ans);
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < act.size(); i++)
~~^~~~~~~~~~~~
islands.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < act.size(); i++) {
~~^~~~~~~~~~~~
islands.cpp:14:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
#define prl(n) printf("%I64d\n", (n))
^
islands.cpp:99:2: note: in expansion of macro 'prl'
prl(ans);
^~~
islands.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ni(n) scanf("%d", &(n))
~~~~~^~~~~~~~~~~~
islands.cpp:55:2: note: in expansion of macro 'ni'
ni(n);
^~
islands.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &par[i], &w[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23804 KB |
Output is correct |
| 2 |
Correct |
24 ms |
23936 KB |
Output is correct |
| 3 |
Incorrect |
22 ms |
23936 KB |
Output isn't correct |
| 4 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 8 |
Incorrect |
23 ms |
23808 KB |
Output isn't correct |
| 9 |
Incorrect |
22 ms |
23936 KB |
Output isn't correct |
| 10 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 11 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
24864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
27260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
36104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
47636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
51620 KB |
Output is correct |
| 2 |
Incorrect |
618 ms |
85468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
367 ms |
87800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
