#include<iostream>
#include<vector>
using namespace std;
vector<int>edge[1212121];
long long RD[1212121], D[1212121], Y[1212121], SV[1212121], L[1212121], V[1212121];
int X[1212121], indeg[1212121], ck[1212121];
long long max(long long a, long long b) { if (a < b)return b; return a; }
long long get_RD(int x) { // O(E)
if (edge[x].size() < 2)return 0;
long long mx1 = 0, mxw, mx2 = 0;
for (int &nxt : edge[x])if (mx1 < D[nxt] + Y[nxt])mx1 = D[nxt] + Y[nxt], mxw = nxt;
for (int &nxt : edge[x])if (nxt != mxw && mx2 < D[nxt] + Y[nxt])mx2 = D[nxt] + Y[nxt];
return mx1 + mx2;
}
int main() {
ios_base::sync_with_stdio(false);
vector<long long>Q;
long long n, i, j; cin >> n;
for (i = 1; i <= n; i++) {
cin >> X[i] >> Y[i], indeg[X[i]]++, edge[X[i]].push_back(i); // E == N
if (X[i] == i)return 0;
}
for (i = 1; i <= n; i++)if (indeg[i] == 0)Q.push_back(i);
while (!Q.empty()) { // O(N)
long long now = Q.back(); Q.pop_back();
if (now == 0)return 0;
RD[now] = max(RD[now], get_RD(now));
RD[X[now]] = max(RD[X[now]], RD[now]);
D[X[now]] = max(D[X[now]], D[now] + Y[now]);
if (--indeg[X[now]] == 0)Q.push_back(X[now]);
ck[now] = 1;
}
long long ans = 0;
for (i = 1; i <= n; i++) if (!ck[i]) { // O(N)
long long now = i, S = 0, sz = 0, res = 0, mx1 = -1e18, mx2 = -1e18;
while (!ck[now]) { // O(Cyc)
L[++sz] = D[now]; V[sz] = Y[now];
res = max(res, max(RD[now], get_RD(now)));
S += Y[now];
ck[now] = 1; now = X[now];
}
for (i = 1; i <= sz; i++)SV[i] = SV[i - 1] + V[i];
for (i = 1; i <= sz; i++) {
res = max(res, max(L[i] + SV[i - 1] + mx1, L[i] + S - SV[i - 1] + mx2));
mx1 = max(mx1, L[i] - SV[i - 1]);
mx2 = max(mx2, L[i] + SV[i - 1]);
}
ans += res;
}
cout << ans;
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:18:18: warning: unused variable 'j' [-Wunused-variable]
long long n, i, j; cin >> n;
^
islands.cpp: In function 'long long int get_RD(int)':
islands.cpp:12:26: warning: 'mxw' may be used uninitialized in this function [-Wmaybe-uninitialized]
for (int &nxt : edge[x])if (nxt != mxw && mx2 < D[nxt] + Y[nxt])mx2 = D[nxt] + Y[nxt];
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
28920 KB |
Output is correct |
2 |
Correct |
25 ms |
28920 KB |
Output is correct |
3 |
Correct |
25 ms |
29008 KB |
Output is correct |
4 |
Correct |
25 ms |
29008 KB |
Output is correct |
5 |
Correct |
24 ms |
29008 KB |
Output is correct |
6 |
Correct |
25 ms |
29040 KB |
Output is correct |
7 |
Correct |
25 ms |
29040 KB |
Output is correct |
8 |
Correct |
25 ms |
29116 KB |
Output is correct |
9 |
Correct |
26 ms |
29116 KB |
Output is correct |
10 |
Correct |
26 ms |
29116 KB |
Output is correct |
11 |
Correct |
26 ms |
29116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
29164 KB |
Output is correct |
2 |
Correct |
27 ms |
29164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
29292 KB |
Output is correct |
2 |
Correct |
27 ms |
29420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
30060 KB |
Output is correct |
2 |
Correct |
41 ms |
31544 KB |
Output is correct |
3 |
Correct |
35 ms |
31544 KB |
Output is correct |
4 |
Correct |
30 ms |
31544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
32508 KB |
Output is correct |
2 |
Correct |
62 ms |
35060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
155 ms |
40948 KB |
Output is correct |
2 |
Correct |
120 ms |
43784 KB |
Output is correct |
3 |
Correct |
201 ms |
47036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
51976 KB |
Output is correct |
2 |
Correct |
252 ms |
61476 KB |
Output is correct |
3 |
Correct |
209 ms |
66940 KB |
Output is correct |
4 |
Correct |
277 ms |
74920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
329 ms |
74920 KB |
Output is correct |
2 |
Correct |
649 ms |
90464 KB |
Output is correct |
3 |
Correct |
413 ms |
90464 KB |
Output is correct |
4 |
Correct |
482 ms |
92896 KB |
Output is correct |
5 |
Correct |
429 ms |
92896 KB |
Output is correct |
6 |
Correct |
917 ms |
92896 KB |
Output is correct |
7 |
Correct |
415 ms |
100124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
408 ms |
100124 KB |
Output is correct |
2 |
Correct |
386 ms |
100124 KB |
Output is correct |
3 |
Correct |
389 ms |
103532 KB |
Output is correct |
4 |
Execution timed out |
2077 ms |
103532 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |