#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const ll INF = 1e18;
struct Edge {
int nod, cst;
int id;
};
vector < vector <Edge> > g;
vector < pair <int, int> > cyc;
vector <int> nodes, vis, deg;
void get_cyc(int nod) {
queue <int> Q;
Q.push(nod), vis[nod] = 1;
while(Q.size()) {
nod = Q.front(), nodes.push_back(nod);
Q.pop();
for(auto it : g[nod]) {
if(vis[it.nod] == 0) {
vis[it.nod] = 1;
Q.push(it.nod);
}
}
}
for(auto it : nodes) {
vis[it] = 0;
if(deg[it] == 1) {
Q.push(it);
vis[it] = 1;
}
}
while(Q.size()) {
nod = Q.front();
Q.pop();
for(auto it : g[nod]) {
deg[it.nod]--;
if(deg[it.nod] == 1) {
Q.push(it.nod);
vis[it.nod] = 1;
}
}
}
for(auto it : nodes) {
if(vis[it] == 0) {
nod = it;
break;
}
}
int root = nod, flag = 1, id = 0;
vis[nod] = 1;
while(flag) {
for(auto it : g[nod]) {
if(vis[it.nod] == 0) {
vis[it.nod] = 1;
cyc.push_back({nod, it.cst});
id = it.id, nod = it.nod;
break;
}
else if(it.nod == root && it.id != id) {
cyc.push_back({nod, it.cst});
flag = 0;
}
}
}
}
vector <ll> dp1, dp2;
void dfs(int nod, ll &ans) {
vector <int> Q;
int sz = 0;
Q.push_back(nod);
vis[nod] = 1;
while(sz < Q.size()) {
nod = Q[sz++];
for(auto it : g[nod]) {
if(vis[it.nod] == 0) {
vis[it.nod] = 2;
Q.push_back(it.nod);
}
}
}
reverse(Q.begin(), Q.end());
for(auto nod : Q) {
dp1[nod] = dp2[nod] = 0;
for(auto it : g[nod]) {
if(vis[it.nod] == 1) {
continue;
}
ll cur = dp1[it.nod] + it.cst;
if(dp1[nod] <= cur) {
dp2[nod] = dp1[nod];
dp1[nod] = cur;
}
else if(dp2[nod] < cur) {
dp2[nod] = cur;
}
}
ans = max(ans, dp1[nod] + dp2[nod]);
}
}
inline ll solve(int nod) {
cyc.clear(), nodes.clear();
get_cyc(nod);
for(auto it : nodes) {
vis[it] = 0;
}
ll sum = 0;
for(auto it : cyc) {
vis[it.first] = 1;
sum += it.second;
}
ll cur = 0, mx1 = -INF, mx2 = -INF, ans = 0;
for(auto it : cyc) {
dfs(it.first, ans);
if(it.first != cyc[0].first) {
ans = max(ans, max(mx1 + dp1[it.first] + cur, mx2 + dp1[it.first] - cur));
}
mx1 = max(mx1, dp1[it.first] - cur);
mx2 = max(mx2, dp1[it.first] + cur + sum);
cur += it.second;
}
return ans;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
g.resize(n + 1), deg.resize(n + 1);
for(i = 1; i <= n; i++) {
int nod, cst;
cin >> nod >> cst;
g[i].push_back({nod, cst, i});
g[nod].push_back({i, cst, i});
deg[i]++, deg[nod]++;
}
vis.resize(n + 1);
dp1.resize(n + 1, -INF), dp2.resize(n + 1, -INF);
ll ans = 0;
for(i = 1; i <= n; i++) {
if(vis[i] == 0) {
ans += solve(i);
}
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
Compilation message
islands.cpp: In function 'void dfs(int, long long int&)':
islands.cpp:92:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sz < Q.size()) {
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1792 KB |
Output is correct |
| 2 |
Correct |
29 ms |
3968 KB |
Output is correct |
| 3 |
Correct |
15 ms |
2432 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
5500 KB |
Output is correct |
| 2 |
Correct |
46 ms |
9592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
19308 KB |
Output is correct |
| 2 |
Correct |
115 ms |
20356 KB |
Output is correct |
| 3 |
Correct |
142 ms |
27308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
35552 KB |
Output is correct |
| 2 |
Correct |
253 ms |
52044 KB |
Output is correct |
| 3 |
Correct |
262 ms |
51840 KB |
Output is correct |
| 4 |
Correct |
343 ms |
68008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
389 ms |
106560 KB |
Output is correct |
| 2 |
Correct |
1468 ms |
103600 KB |
Output is correct |
| 3 |
Correct |
373 ms |
82852 KB |
Output is correct |
| 4 |
Correct |
520 ms |
111208 KB |
Output is correct |
| 5 |
Correct |
528 ms |
113736 KB |
Output is correct |
| 6 |
Execution timed out |
2048 ms |
108772 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
437 ms |
88760 KB |
Output is correct |
| 2 |
Correct |
424 ms |
88676 KB |
Output is correct |
| 3 |
Correct |
462 ms |
90976 KB |
Output is correct |
| 4 |
Correct |
528 ms |
78716 KB |
Output is correct |
| 5 |
Correct |
497 ms |
101992 KB |
Output is correct |
| 6 |
Correct |
621 ms |
90092 KB |
Output is correct |
| 7 |
Execution timed out |
2092 ms |
108052 KB |
Time limit exceeded |
