比赛 EYOI暨SBOI暑假快乐赛4th 评测结果 AAAAAAAAAA
题目名称 醉笑圣城书 最终得分 100
用户昵称 Restly 运行时间 0.748 s
代码语言 C++ 内存使用 61.44 MiB
提交时间 2022-06-28 09:24:46
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
using namespace std;
const int maxn = 2e5 + 5;
vector<pair<int,long long> > g[maxn];
typedef long long ll;
struct edge {
    int u,v;
    ll t;
    edge() {
        u = v = t = 0;
    }
    edge(int u,int v,ll t):u(u),v(v),t(t){}
}E[maxn];
int n,m;
ll s;
int pre[maxn],lg[maxn],f[maxn][20],d[maxn];
ll p[maxn][20];
int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void dfs(int u,int fa) {
    for(auto cur : g[u]) {
        int v = cur.fir;
        ll w = cur.sec;
        if(v == fa)continue ;
        f[v][0] = u;
        p[v][0] = w;
        d[v] = d[u] + 1;
        for(int k = 1;(1 << k) <= d[v];++ k)
            f[v][k] = f[f[v][k - 1]][k - 1],p[v][k] = max(p[v][k - 1] , p[f[v][k - 1]][k - 1]);
        dfs(v , u);
    }
    return ;
}
ll findmax(int u,int v) {
    ll ans = 0;
    if(d[u] < d[v])swap(u , v);
    for(int k = lg[d[u]];~ k;-- k) {
        if(d[u] - (1 << k) >= d[v]) {
            ans = max(ans , p[u][k]);
            u = f[u][k];
        }
        if(u == v)return ans;
    }
    for(int k = lg[d[u]];~ k;-- k) {
        if(f[u][k] != f[v][k]) {
            ans = max(ans , max(p[u][k] , p[v][k]));
            u = f[u][k];
            v = f[v][k];
        }
    }
    return max(ans , max(p[u][0] , p[v][0]));
}
int main() {
    freopen("zxscs.in","r",stdin);
    freopen("zxscs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++ i)pre[i] = i;
    for(int i = 2;i <= n;++ i)lg[i] = lg[i >> 1] + 1;
    for(int i = 1;i <= m;++ i) {
        scanf("%d%d%lld",&E[i].u,&E[i].v,&E[i].t);
    }
    scanf("%lld",&s);
    sort(E + 1 , E + 1 + m , [](edge x,edge y){return x.t < y.t;});
    ll ans = 0;
    int r1 = 0,r2 = 0;
    for(int i = 1;i <= m;++ i) {
        if(E[i].t == -1) {
            r1 = E[i].u;
            r2 = E[i].v;
            continue ;
        }
        int u = find(E[i].u),v = find(E[i].v);
        if(u != v) {
            pre[v] = u;
            ans += E[i].t;
            g[E[i].u].pb(mp(E[i].v , E[i].t));
            g[E[i].v].pb(mp(E[i].u , E[i].t));
        }
    }
    if(s >= ans) {
        puts("Poor van!");
        return 0;
    }
    ll delta = ans - s;
    dfs(1 , 0);
    ans = findmax(r1 , r2);
    if(ans > delta)printf("%lld\n",ans - delta);
    else puts("Poor van!");
    fclose(stdin);
    fclose(stdout);
    return 0;
}