#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int dydis = 1e6 + 100;
const long long inf = 1000000000000000000;
int n;
int ind;
long long opcija, pries, pgl, delta;
vector<pair<int, int> > grafas[dydis];
int gr[dydis] = {0};
int wh[dydis] = {0};
bool vis[dydis] = {0};
bool visited[dydis] = {0};
bool inCycle[dydis] = {0};
long long cycVal[dydis] = {0};
long long pref[dydis], suf[dydis];
multiset<long long> pirmas, antras;
void dfs(int v, int prim) {
queue<int> q;
q.push(v);
while (!q.empty()) {
v = q.front();
q.pop();
if (visited[v]) {
continue;
}
visited[v] = 1;
for (auto x : grafas[v]) {
if (visited[x.first]) {
continue;
}
q.push(x.first);
}
}
}
vector<int> cNodes, cNodes1;
bool fd = 0;
void findCycle(int v) {
if (fd) {
return;
}
if (vis[v]) {
cNodes.push_back(v);
fd = 1;
return;
}
if (!fd) {
cNodes.push_back(v);
}
vis[v] = 1;
findCycle(gr[v]);
if (!fd) {
cNodes.pop_back();
}
}
long long otherVal = 0;
long long dfs1(int v, int came) {
long long ret = 0;
long long mx1 = 0;
long long mx2 = 0;
for (auto x : grafas[v]) {
if (x.first == came) {
continue;
}
long long opcija = dfs1(x.first, v) + x.second;
if (opcija > mx1) {
mx2 = mx1;
mx1 = opcija;
}
else if (opcija > mx2) {
mx2 = opcija;
}
ret = max(ret, opcija);
}
otherVal = max(otherVal, mx1 + mx2);
return ret;
}
void removeVal(multiset<long long> &st, long long val) {
auto itr = st.find(val);
if (itr != st.end()) {
st.erase(itr);
}
}
bool yraKairej[dydis] = {0};
long long sm1, sm2, st, atsak, mx1, mx2, sum, m, did1, did2;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
a--;
gr[i] = a;
wh[i] = b;
grafas[a].push_back({i, b});
grafas[i].push_back({a, b});
}
atsak = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) {
continue;
}
dfs(i, i);
cNodes1.clear();
cNodes.clear();
fd = 0;
findCycle(i);
bool can = 0;
for (auto x : cNodes) {
if (x == cNodes.back()) {
can = 1;
}
if (can) {
cNodes1.push_back(x);
}
}
cNodes1.pop_back();
for (auto x : cNodes1) {
inCycle[x] = 1;
}
otherVal = 0;
for (auto x : cNodes1) {
cycVal[x] = 0;
mx1 = 0, mx2 = 0;
for (auto y : grafas[x])
if (!inCycle[y.first]) {
opcija = dfs1(y.first, x) + y.second;
cycVal[x] = max(cycVal[x], opcija);
if (opcija > mx1) {
mx2 = mx1;
mx1 = opcija;
}
else if (opcija > mx2) {
mx2 = opcija;
}
otherVal = max(otherVal, mx1 + mx2);
}
}/*
cout << i << " cycle = ";
for(auto x : cNodes1){
cout << "{" << x << ", " << cycVal[x] << "} ";
}
cout << endl << endl;*/
sum = 0;
for (auto x : cNodes1) {
sum += wh[x];
}
m = cNodes1.size();
st = 0;
pref[0] = 0;
suf[m - 1] = 0;
for (int j = 1; j < m; j++) {
pref[j] = pref[j - 1] + wh[cNodes1[j - 1]];
}
for (int j = m - 2; j > -1; j--) {
suf[j] = suf[j + 1] + wh[cNodes1[j]];
}
// ats1 = mas[i] + mas[j] + pref[j] - pref[i]
// ats1 = (mas[i] - pref[i]) + (mas[j]+pref[j])
//
// ats2 = (pref[i] + mas[i] + x) + suf[j] + mas[j]
for (int j = 0; j < m; j++) {
pirmas.insert(cycVal[cNodes1[j]] + pref[j]);
antras.insert(cycVal[cNodes1[j]] + suf[j]);
}
for (int j = 0; j < m - 1; j++) {
removeVal(pirmas, cycVal[cNodes1[j]] + pref[j]);
removeVal(antras, cycVal[cNodes1[j]] + suf[j]);
did1 = (*pirmas.rbegin()) + cycVal[cNodes1[j]] - pref[j];
did2 = (*antras.rbegin()) + pref[j] + wh[cNodes1[m - 1]] + cycVal[cNodes1[j]];
st = max(st, max(did1, did2));
}
removeVal(pirmas, cycVal[cNodes1[m - 1]] + pref[m - 1]);
removeVal(antras, cycVal[cNodes1[m - 1]] + suf[m - 1]);
st = max(st, otherVal);
atsak += st;
// cout << "DONE" << endl << endl << endl;
}
cout << atsak;
return 0;
}
/*
* 1) kai pridedu nauja node'a, jo reiksme bus atstumas iki pirmosios (pagal laikr. ) + cycVal[x]
* 2) kai pasalinu nauja node'a, jo reiksme bus
*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23768 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23884 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23944 KB |
Output is correct |
| 4 |
Correct |
17 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
16 ms |
23756 KB |
Output is correct |
| 6 |
Correct |
16 ms |
23748 KB |
Output is correct |
| 7 |
Correct |
16 ms |
23884 KB |
Output is correct |
| 8 |
Correct |
17 ms |
23780 KB |
Output is correct |
| 9 |
Correct |
17 ms |
23784 KB |
Output is correct |
| 10 |
Correct |
17 ms |
23804 KB |
Output is correct |
| 11 |
Correct |
17 ms |
23868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23916 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23944 KB |
Output is correct |
| 2 |
Correct |
19 ms |
24268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
24892 KB |
Output is correct |
| 2 |
Correct |
40 ms |
27872 KB |
Output is correct |
| 3 |
Correct |
31 ms |
25036 KB |
Output is correct |
| 4 |
Correct |
21 ms |
24456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
29332 KB |
Output is correct |
| 2 |
Correct |
73 ms |
31804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
37572 KB |
Output is correct |
| 2 |
Correct |
175 ms |
45040 KB |
Output is correct |
| 3 |
Correct |
202 ms |
58640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
47668 KB |
Output is correct |
| 2 |
Correct |
310 ms |
79736 KB |
Output is correct |
| 3 |
Correct |
583 ms |
89060 KB |
Output is correct |
| 4 |
Correct |
512 ms |
113192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
75812 KB |
Output is correct |
| 2 |
Runtime error |
718 ms |
131076 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
426 ms |
126436 KB |
Output is correct |
| 2 |
Correct |
414 ms |
90272 KB |
Output is correct |
| 3 |
Runtime error |
460 ms |
131076 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
