比赛 |
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;
}