| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684099 |
2023-01-20T11:18:10 Z |
starplat |
Islands (IOI08_islands) |
C++14 |
|
468 ms |
131072 KB |
#include <bits/stdc++.h>
#define mid (x+y)/2
using namespace std;
int n,vis[1000005],bck[1000005],no[1000005];
int done,pt,cycle[1000005],dsu[1000005],is[1000005];
vector<pair<int,long long> > g[1000005];
long long sum,dp[1000005],dist_mx[1000005],dist_mx1[1000005];
long long seg[4000005],lz[4000005],we[1000005],pw[1000005];
int find(int x){
if (x==dsu[x]) return x;
else return dsu[x]=find(dsu[x]);
}
void dfs(int x,int p){
if (done) return;
if (vis[x]) {
done=true;
int ct=0;
for (pair<int,long long> i:g[x]){
if (i.first==p) ++ct;
}
if (ct>1){
cycle[++pt]=x;
cycle[++pt]=p;
is[x]=true; is[p]=true;
return;
}
while (p!=x){
is[p]=true;
cycle[++pt]=p;
p=bck[p];
if (p==-1) break;
}
is[x]=true;
cycle[++pt]=x;
}
else {
vis[x]=1; bck[x]=p;
for (pair<int,long long> i:g[x]) {
if (i.first!=p) dfs(i.first,x);
}
}
}
void treedp(int x,int p){
for (pair<int,long long> i:g[x]){
if (is[i.first]) continue;
if (i.first!=p) treedp(i.first,x);
}
for (pair<int,long long> i:g[x]){
if (is[i.first]) continue;
if (i.first!=p) dp[x]=max(dp[x],dp[i.first]+i.second);
}
}
int node;
void dfs_mx(int x,int p){
if (dist_mx[x]>dist_mx[node]) node=x;
for (pair<int,long long> i:g[x]){
if (is[i.first]) continue;
if (i.first!=p) {
dist_mx[i.first]=dist_mx[x]+i.second;
dfs_mx(i.first,x);
}
}
}
void diameter(int x,int p){
if (dist_mx1[x]>dist_mx1[node]) node=x;
for (pair<int,long long> i:g[x]){
if (is[i.first]) continue;
if (i.first!=p){
dist_mx1[i.first]=dist_mx1[x]+i.second;
diameter(i.first,x);
}
}
}
long long weight(int x,int tar){
for (pair<int,long long> k:g[x]){
if (k.first==tar) return k.second;
}
}
void lzprog(int pos,long long v){
lz[pos*2]+=v; lz[pos*2+1]+=v;
}
void update(int id,int x,int y,int l,int r,long long v){
if (lz[id]){
seg[id]+=lz[id];
if (x!=y) lzprog(id,lz[id]);
lz[id]=0;
}
if (x>y || y<l || x>r) return;
if (l<=x && y<=r){
seg[id]+=v;
lzprog(id,v);
return;
}
update(id*2,x,mid,l,r,v);
update(id*2+1,mid+1,y,l,r,v);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
long long query(int id,int x,int y,int l,int r){
if (lz[id]){
seg[id]+=lz[id];
if (x!=y) lzprog(id,lz[id]);
lz[id]=0;
}
if (x>y || y<l || x>r) return 0;
if (l<=x && y<=r) return seg[id];
else return max(query(id*2,x,mid,l,r),query(id*2+1,mid+1,y,l,r));
}
void build(int id,int x,int y){
lz[id]=0;
if (x==y) seg[id]=dp[cycle[x]];
else {
build(id*2,x,mid);
build(id*2+1,mid+1,y);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
}
long long work(){
build(1,1,pt);
long long sum=0; long long b=0;
for (int j=1;j<pt;j++) we[j]=weight(cycle[j],cycle[j+1]),sum+=we[j];
we[pt]=weight(cycle[pt],cycle[1]); sum+=we[pt];
for (int j=pt-1;j>=1;j--) update(1,1,pt,j+1,pt,we[j]);
for (int j=1;j<=pt;j++){
b=max(b,query(1,1,pt,j+1,pt)+dp[cycle[j]]);
b=max(b,query(1,1,pt,1,j-1)+dp[cycle[j]]);
update(1,1,pt,j+1,pt,-we[j]);
update(1,1,pt,1,j-1,-we[j]);
sum-=we[j]; update(1,1,n,j,j,sum);
}
return b;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) dsu[i]=i;
for (int i=1;i<=n;i++){
int x; long long w;
scanf("%d%lld",&x,&w);
dsu[find(i)]=find(x);
g[i].emplace_back(make_pair(x,w));
g[x].emplace_back(make_pair(i,w));
bck[i]=-1; is[i]=no[i]=false;
}
for (int i=1;i<=n;i++){
if (no[find(i)]) continue;
pt=0; done=false;
no[find(i)]=true;
dfs(i,-1);
long long mx=0;
if (!done) {
node=i;
dfs_mx(node,-1);
diameter(node,-1);
mx=dist_mx1[node];
}
else {
for (int j=1;j<=pt;j++) {
treedp(cycle[j],-1);
for (pair<int,long long> k:g[cycle[j]]){
if (is[k.first]) continue;
node=k.first;
dfs_mx(node,-1);
diameter(node,-1);
mx=max(mx,dist_mx1[node]);
}
}
if (pt==2){
long long tmp=0;
for (pair<int,long long> k:g[cycle[1]]) {
if (is[k.first]) tmp=max(tmp,k.second);
}
mx=max(mx,dp[cycle[1]]+dp[cycle[2]]+tmp);
}
else {
mx=max(mx,work());
reverse(cycle+1,cycle+1+pt);
mx=max(mx,work());
}
}
sum+=mx;
}
printf("%lld\n",sum);
}
Compilation message
islands.cpp: In function 'long long int weight(int, int)':
islands.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
78 | }
| ^
islands.cpp: In function 'int main()':
islands.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
islands.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d%lld",&x,&w);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23868 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23892 KB |
Output isn't correct |
| 3 |
Incorrect |
15 ms |
23932 KB |
Output isn't correct |
| 4 |
Correct |
13 ms |
23768 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
23772 KB |
Output isn't correct |
| 6 |
Correct |
13 ms |
23880 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
23764 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
23840 KB |
Output isn't correct |
| 9 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 10 |
Incorrect |
13 ms |
23772 KB |
Output isn't correct |
| 11 |
Correct |
13 ms |
23820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
25700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
31824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
46364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
468 ms |
60188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
105856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
357 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
