| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 53763 | ics0503 | Islands (IOI08_islands) | C11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
long long max(long long a, long long b) { if (a < b)return b; return a; }
long long get_RD(int x) {
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);
for (i = 1; i <= n; i++)if (indeg[i] == 0)Q.push_back(i);
while (!Q.empty()) {
long long now = Q.back(); Q.pop_back();
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]);
X[now] = 0;
}
long long ans = 0;
for (i = 1; i <= n; i++) if(X[i]){
long long now = i, S = 0, sz = 0, res = 0, mx1 = -1e18,mx2 = -1e18;
while (X[now]) {
L[++sz] = D[now]; V[sz] = Y[now];
res = max(res, max(RD[now], get_RD(now)));
S += Y[now];
long long tmp = now; now = X[now]; X[tmp] = 0;
}
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;
}