#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long LL;
const int maxn = 1e6+5;
vii adj[maxn];
bool vis[maxn];
bool incycle[maxn];
bool spec[maxn];
int sz[maxn];
LL dp[maxn];
vi cycle;
int mark[maxn];
int Pair[maxn];
LL bestlen[maxn];
LL ndbest[maxn];
vector< LL > len;
int cnt(int u)
{
if(vis[u]) return 0;
vis[u] = 1;
int res = 0;
for(int i = 0; i< (int) adj[u].size(); i++)
{
int v = adj[u][i].X;
res += cnt(v);
}
return res+1;
}
int find(int u, int p)
{
if(vis[u]) return u;
vis[u] = 1;
int fak = -1;
for(int i = 0; i< (int) adj[u].size(); i++)
{
int v = adj[u][i].X, w = adj[u][i].Y;
if(v == p) continue;
int k = find(v, u);
if(k != -1) fak = k;
if(k != -1)
{
incycle[u] = 1;
cycle.pb(u);
len.pb(w);
}
}
if(fak == u) return -1;
return fak;
}
LL val(int u, int p)
{
if(incycle[u] && p) return -4e18;
if(dp[u] != -1) return dp[u];
dp[u] = 0;
for(int i = 0; i< (int) adj[u].size(); i++)
{
int v = adj[u][i].X, w = adj[u][i].Y;
if(v == p) continue;
dp[u] = max(dp[u], w+val(v, u));
}
return dp[u];
}
LL findNDbest(int u, int p)
{
if(incycle[u] && p) return -4e18;
if(ndbest[u] != -1) return ndbest[u];
LL best, ndbesT;
best = ndbesT = 0;
for(int i = 0; i< (int) adj[u].size(); i++)
{
int v = adj[u][i].X, w = adj[u][i].Y;
if(v == p) continue;
LL here = w+val(v, u);
if(here> best)
{
ndbesT = best;
best = here;
}
else if(here> ndbesT)
{
ndbesT = here;
}
}
return ndbest[u] = ndbesT;
}
map<pair<int,int>, LL> lens;
int main()
{
memset(dp, -1, sizeof dp);
memset(ndbest, -1, sizeof ndbest);
int n; scanf("%d", &n);
for(int i = 1; i<= n; i++)
{
int u, w;
scanf("%d %d", &u, &w);
if(mark[i] == u)
{
spec[u] = spec[i] = 1;
Pair[u] = i;
Pair[i] = u;
}
adj[i].pb(ii(u, w));
adj[u].pb(ii(i, w));
mark[u] = i;
}
for(int i = 1; i<= n; i++)
{
if(vis[i]) continue;
sz[i] = cnt(i);
}
memset(vis, 0, sizeof vis);
LL res = 0;
for(int i = 1; i<= n; i++)
{
if(spec[i] && vis[i] == 0)
{
assert(0);
cnt(i);
incycle[i] = incycle[Pair[i]] = 1;
//printf("%d %d\n", i, Pair[i]);
//printf("---%lld\n", bestlen[Pair[i]]);
//printf("%lld %lld\n", val(Pair[i], 0), findNDbest(Pair[i], 0));
LL lens = 0;
for(int j = 0; j< (int) adj[i].size(); j++)
{
if(adj[i][j].X == Pair[i]) lens = max(lens, (LL)adj[i][j].Y);
}
res += max(val(i, 0)+val(Pair[i], 0)+lens, max(val(i, 0)+findNDbest(i, 0), val(Pair[i], 0)+findNDbest(Pair[i], 0)));
//printf("%lld\n", res);
}
}
for(int i = 1; i<= n; i++)
{
if(vis[i]) continue;
cycle.clear(); len.clear();
//printf("%d\n", i);
find(i, 0);
deque<pair<LL, int> > foo;
LL run = 0;
LL best = 0;
cycle.pop_back(); len.pop_back();
int maxlen = cycle.size();
//for(int j = 0; j< (int) cycle.size(); j++) printf("%d ", cycle[j]);
//printf("\n");
//for(int j = 0; j< (int) len.size(); j++) printf("%lld ", len[j]);
for(int j = 0; j< (int) cycle.size(); j++)
{
int u = cycle[j];
LL ton = j?len[j]:0;
run += ton;
//printf("%d: %lld\n", u, val(u, 0));
while(!foo.empty() && j-foo.front().Y>= maxlen) foo.pop_front();
if(!foo.empty())best = max(best, val(u, 0)+run+foo.front().X);
while(!foo.empty() && foo.back().X<= val(u, 0)-run) foo.pop_back();
foo.push_back(mp(val(u, 0)-run, j));
best = max(best, val(u, 0)+findNDbest(u, 0));
}
for(int j = maxlen; j< 2*maxlen; j++)
{
int u = cycle[j-maxlen];
LL ton = len[j-maxlen];
run += ton;
while(!foo.empty() && j-foo.front().Y>= maxlen) foo.pop_front();
if(!foo.empty())best = max(best, val(u, 0)+run+foo.front().X);
while(!foo.empty() && foo.back().X<= val(u, 0)-run) foo.pop_back();
foo.push_back(mp(val(u, 0)-run, j));
}
res += best;
//printf("%lld\n", res);
}
printf("%lld\n", res);
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &w);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
81656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Incorrect |
39 ms |
40440 KB |
Output isn't correct |
| 3 |
Correct |
39 ms |
40480 KB |
Output is correct |
| 4 |
Runtime error |
95 ms |
81656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Correct |
38 ms |
40568 KB |
Output is correct |
| 6 |
Runtime error |
92 ms |
81756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
95 ms |
81772 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
39 ms |
40432 KB |
Output isn't correct |
| 9 |
Runtime error |
93 ms |
81656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
93 ms |
81756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
93 ms |
81768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
40560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
81864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
41564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
45348 KB |
Output is correct |
| 2 |
Correct |
91 ms |
47808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
53408 KB |
Output is correct |
| 2 |
Correct |
167 ms |
59192 KB |
Output is correct |
| 3 |
Incorrect |
200 ms |
70784 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
244 ms |
64044 KB |
Output is correct |
| 2 |
Correct |
325 ms |
86032 KB |
Output is correct |
| 3 |
Correct |
363 ms |
95464 KB |
Output is correct |
| 4 |
Correct |
445 ms |
118536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
536 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
562 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
