제출 #684099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684099		starplat	Islands (IOI08_islands)	C++14	15 / 100	468 ms	131072 KiB

islands

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10