/*
Problem: P4381 [IOI2008] Island
When: 2023-11-19 19:41:26
Author: Ning07
*/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
namespace fast{
#pragma GCC optimize(Ofast)
#pragma GCC optimization (unroll-loops)
#pragma GCC target(avx,avx2,fma)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
}
using namespace fast;
inline string read_string(){
char ch=getchar(); string st1="";
while (!((ch>='A') && (ch<='Z'))) ch=getchar();
while ((ch>='A') && (ch<='Z')) st1+=ch,ch=getchar();
return st1;
}
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename T> inline void re(T &x){ x = 0; T f = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) {x = x * (1<<1) + x*(1<<3) + (ch-48) ; ch = getchar();} x *= f; }
template<typename x,typename... y>void re(x& a,y&... b){re(a);re(b...);}
template<typename T> inline void ps(T x) { if(x < 0){ putchar('-'); x = -x; } if(x > 9) ps(x / 10); putchar(x % 10 + '0');}
template<typename x,typename... y>void ps(x& a,y&... b){ps(a); putchar(' '); ps(b...);}
#define sp putchar(' ')
#define nl putchar('\n')
const int NN=1e6+1;
int N, A[NN], deg[NN], W[NN];
i64 ans, f[NN], g[NN];
i64 get(int p){
int st=p; p=A[p];
i64 m1=f[st],m2=f[st];
i64 s=W[st],ans1=g[st],ans2=-1E18;
while (p != st) {
deg[p] = 0;
ans1=max(ans1,max(g[p],f[p]+s+m1));
ans2=max(ans2,f[p]-s+m2);
m1=max(m1,f[p]-s),m2=max(m2,f[p]+s);
s+=W[p],p=A[p];
}
return max(ans1,ans2+s);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
re(N);
for(int i=1;i<=N;i++){
re(A[i],W[i]);
++deg[A[i]];
}
queue<int> q;
for(int i=1;i<=N;i++) if(!deg[i]) q.push(i);
while (!q.empty()){
int p=q.front(); q.pop();
i64 c=f[p]+W[p];
g[A[p]]=max(g[A[p]],max(f[A[p]]+c,g[p]));
f[A[p]]=max(f[A[p]],c);
if (!--deg[A[p]]) q.push(A[p]);
}
for(int i=1;i<=N;i++) if(deg[i]) ans += get(i);
ps(ans);
}
Compilation message
islands.cpp:13: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
13 | #pragma GCC optimization (unroll-loops)
|
islands.cpp:12:26: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
12 | #pragma GCC optimize(Ofast)
| ^~~~~
islands.cpp:14:24: warning: '#pragma GCC option' is not a string [-Wpragmas]
14 | #pragma GCC target(avx,avx2,fma)
| ^~~
islands.cpp:15:24: warning: '#pragma GCC option' is not a string [-Wpragmas]
15 | #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
| ^~~
islands.cpp:35:43: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
35 | #pragma GCC optimize("-fwhole-program")
| ^
islands.cpp:42:45: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
42 | #pragma GCC optimize("-fstrict-overflow")
| ^
islands.cpp:44:45: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
44 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
islands.cpp:58:55: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
58 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
islands.cpp:64:27: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
64 | inline string read_string(){
| ^
islands.cpp:64:27: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:64:27: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:64:27: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
islands.cpp:72:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
72 | template<typename T> inline void re(T &x){ x = 0; T f = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) {x = x * (1<<1) + x*(1<<3) + (ch-48) ; ch = getchar();} x *= f; }
| ^
islands.cpp:72:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:72:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:72:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
islands.cpp:73:55: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
73 | template<typename x,typename... y>void re(x& a,y&... b){re(a);re(b...);}
| ^
islands.cpp:73:55: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:73:55: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:73:55: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
islands.cpp:74:40: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
74 | template<typename T> inline void ps(T x) { if(x < 0){ putchar('-'); x = -x; } if(x > 9) ps(x / 10); putchar(x % 10 + '0');}
| ^
islands.cpp:74:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:74:40: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:74:40: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
islands.cpp:75:55: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
75 | template<typename x,typename... y>void ps(x& a,y&... b){ps(a); putchar(' '); ps(b...);}
| ^
islands.cpp:75:55: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:75:55: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:75:55: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
islands.cpp:82:14: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
82 | i64 get(int p){
| ^
islands.cpp:82:14: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:82:14: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:82:14: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
islands.cpp:95:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
95 | int main(){
| ^
islands.cpp:95:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
islands.cpp:95:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
islands.cpp:95:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 10 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 11 |
Correct |
1 ms |
8536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9560 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9564 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12336 KB |
Output is correct |
| 3 |
Correct |
11 ms |
16988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
22284 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25692 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18264 KB |
Output is correct |
| 4 |
Correct |
25 ms |
27780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
20976 KB |
Output is correct |
| 2 |
Correct |
39 ms |
26708 KB |
Output is correct |
| 3 |
Correct |
32 ms |
29528 KB |
Output is correct |
| 4 |
Correct |
40 ms |
33104 KB |
Output is correct |
| 5 |
Correct |
37 ms |
33372 KB |
Output is correct |
| 6 |
Correct |
88 ms |
32348 KB |
Output is correct |
| 7 |
Correct |
36 ms |
32852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
31312 KB |
Output is correct |
| 2 |
Correct |
32 ms |
31288 KB |
Output is correct |
| 3 |
Correct |
24 ms |
16728 KB |
Output is correct |
| 4 |
Correct |
23 ms |
16732 KB |
Output is correct |
| 5 |
Correct |
32 ms |
32500 KB |
Output is correct |
| 6 |
Correct |
46 ms |
32592 KB |
Output is correct |
| 7 |
Correct |
88 ms |
32596 KB |
Output is correct |
