岛屿

• 第一行包含N个整数，即公园内岛屿的数目。岛屿由1到N编号。
• 随后的N行每一行用来表示一个岛。第i 行由两个以单空格分隔的整数，表示由岛i筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度Li。你可以假设对於每座桥，其端点总是位于不同的岛上。

你的程序必须向标准输出写出包含一个整数的单一行，即可能的最大步行距离。注1：对某些测试，答案可能无法放进32-bit整数，你要取得这道题的满分，可能需要用Pascal的int64或C/C++的long long类型。注2：在比赛环境运行Pascal程序，由标准输入读入64-bit数据比32-bit数据要慢得多，即使被读取的数据可以32-bit表示。我们建议把输入数据读入到32-bit数据类型。评分 N不会超过4,000。

C++11(clang++ 3.9) 解法, 执行用时: 547ms, 内存消耗: 40680K, 提交时间: 2020-03-02 16:16:27

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int par[N],deg[N],edge[N];
 
int n,vis[N];
ll dis[N];
void topsort() {
    queue<int> q;
    for(int i=1; i<=n; ++i)
        if(!deg[i])q.push(i),vis[i]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        int y=par[x];
        if(dis[y]<dis[x]+edge[x])
            dis[y]=dis[x]+edge[x];
        if(--deg[y]==0) {
            vis[y]=1;q.push(y);
        }
    }
}
 
ll d[2*N],b[2*N];
int q[2*N],a[2*N],tot=0,head,tail;
 
ll solve() {
    topsort();
    ll ans=0;
    for(int i=1; i<=n; ++i) {
        if(vis[i])continue;
        tot=0;
        int x=i;
        while(vis[x]<2) {
            a[++tot]=x;
            ++vis[x];
            x=par[x];
        }
        head=0;tail=-1;
        q[++tail]=0;
        ll tmp=0;
        for(int i=1; i<=tot; ++i) {
            if(i-q[head]>=(tot>>1))++head;
            d[i]=d[i-1]+edge[a[i-1]];
            tmp=max(tmp,dis[a[i]]+d[i]-b[q[head]]);
            b[i]=d[i]-dis[a[i]];
            while(head<=tail&&b[q[tail]]>=b[i])--tail;
            q[++tail]=i;
        }
        ans+=tmp;
    }
    return ans;
}
 
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%d%d",par+i,edge+i),++deg[par[i]];
    printf("%lld\n",solve());
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 347ms, 内存消耗: 56140K, 提交时间: 2019-10-05 18:55:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int par[N],deg[N],edge[N];

int n,vis[N];
ll dis[N];
void topsort() {
    queue<int> q;
    for(int i=1; i<=n; ++i)
        if(!deg[i])q.push(i),vis[i]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        int y=par[x];
        if(dis[y]<dis[x]+edge[x])
            dis[y]=dis[x]+edge[x];
        if(--deg[y]==0) {
            vis[y]=1;q.push(y);
        }
    }
}

ll d[2*N],b[2*N];
int q[2*N],a[2*N],tot=0,head,tail;

ll solve() {
    topsort();
    ll ans=0;
    for(int i=1; i<=n; ++i) {
        if(vis[i])continue;
        tot=0;
        int x=i;
        while(vis[x]<2) {
            a[++tot]=x;
            ++vis[x];
            x=par[x];
        }
        head=0;tail=-1;
        q[++tail]=0;
        ll tmp=0;
        for(int i=1; i<=tot; ++i) {
            if(i-q[head]>=(tot>>1))++head;
            d[i]=d[i-1]+edge[a[i-1]];
            tmp=max(tmp,dis[a[i]]+d[i]-b[q[head]]);
            b[i]=d[i]-dis[a[i]];
            while(head<=tail&&b[q[tail]]>=b[i])--tail;
            q[++tail]=i;
        }
        ans+=tmp;
    }
    return ans;
}

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%d%d",par+i,edge+i),++deg[par[i]];
    printf("%lld\n",solve());
    return 0;
}

详情