一场由老年机引发的惨案

· · 生活·游记

众所周知，杭师大下沙校区有优良的电脑。

CSP-S 2025 T2

开考二十分钟秒杀T1，自信看T2，一眼（指花了整整十多分钟）就看出了性质。

花费大概30分钟左右证明了性质（我是废物），码了20分钟。

这是我当时的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10,M=1e6+10;
int read(){
    int x=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x;
}
int n,m,k,f[N],tag[N],need,now,ans,val[N],mi;
struct Node{int x,y,val;}x[M],a[N];
bool cmp(Node x,Node y){return x.val<y.val;}
int finds(int x){return (f[x]==x?x:f[x]=finds(f[x]));}
signed main(){
    n=read();m=read();k=read();
    for (int i=1;i<=m;i++) x[i].x=read(),x[i].y=read(),x[i].val=read();
    sort(x+1,x+m+1,cmp);now=0;
    for (int i=1;i<=n;i++) f[i]=i; 
    for (int i=1;i<=m;i++){
        int fx=finds(x[i].x),fy=finds(x[i].y);
        if (fx==fy) continue;
        f[fx]=fy;ans+=x[i].val;now++;
        a[now]=x[i];
        if (now==n-1) break;
    }
    mi=ans;m=n-1;
    for  (int i=1;i<=k;i++){
        val[i]=read();
        for (int j=1;j<=n;j++) a[++m].val=read(),a[m].x=n+i,a[m].y=j;
    }
    sort(a+1,a+m+1,cmp);
    for (int i=1;i<(1<<k);i++){
        ans=0;now=0;need=n;
        for (int j=1;j<=n+k;j++) f[j]=j;
        for (int j=1,ii=i;j<=k;j++,ii>>=1)
            if (ii&1) ans+=val[j],tag[j]=1,need++;
            else tag[j]=0;
        for (int j=1;j<=m;j++){
            if (a[j].x>n&&tag[a[j].x-n]==0) continue;
            int fx=finds(a[j].x),fy=finds(a[j].y);
            if (fx==fy) continue;
            f[fx]=fy;ans+=a[j].val;now++;
            if (now==need-1) break;
        }
        mi=min(mi,ans);
    }
    printf("%lld\n",mi);
    return 0;
}

洛谷评测记录，极限数据 500ms 左右。

但是！这个代码，杭师大机子大样例都能给我跑 1300ms。

极限数据更是到达了恐怖的 11200ms

（其实当时无意间发现快读加不加能差 3000ms 我已经察觉到不对劲了）

老师常常教导我们，试卷是不会出错的，你们要找自己的问题。

机子再慢，如果你的算法够优的话，也不可能会让你跑到十多秒啊。

于是我开始找自己的问题。

考虑到每次询问都是用更短的边去替换长边，会对当前边产生影响的点应该分属于这条边两个端点的两个子树。

于是考虑直接把两个端点转到根节点，删边再连边。（没错我写了个动态树）

反正就是一通乱搞，大样例都没过，还浪费了两个多小时......

其实现在想想说不定是可做的，但是也没必要再想下去了。

最后是交了逆天动态树优化，直接挂大分。（因为我傻逼暴力没存）

于是杭师大老年机成功的导致一只小杨轻轻地似去了。

考点的机子能不能不要再背刺我了啊TAT