\(\color{white}{\mathbb{霞光划破暗淡天际，月影彷徨，鸡鸣仿佛，冀之以继往开来，名之以：黎明}}\)

今天似乎取得了有史以来最好的成绩~

前两名都 A 掉了 \(t3\)，然鹅 \(t3\) 上去就被我弃了……

前两天部分分都写得比较顺利

\(t1\) 一眼以为 \(bitset\) 裸题，开了 \(6e4 * 6e4\) 直接自信提交，后来一算才发现空间炸了

但是不记得一位 \(bitset\) 是多大，以为和 \(bool\) 一样，只能开 \(10^4 * 10^4\)，没敢打另外 20% 的部分分，暴挂20分

\(t2\) 网络流板子忘得差不多了，口胡了还几次才过了样例

---

A. 世界线

读懂题很快就能看出来是 \(bitset\)，但是空间比较卡

首先，\(bitset\) 是每8位占用一个字节，一次运算复杂度为 \(n/32\)

那么其实前 \(60%\) 都是可以轻松水过去的

发现最后两个点的理论空间都比能开下的 \(bitset\) 大一倍，那么可以采用把所有点分成两部分的方式统计，\(bitset\) 只开一半，第一次统计所有点能到达的 \(\le n/2\) 的点的个数，再来一次统计能到达的 \(>n/2\) 的点的个数，直接相加即可

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e4+5;
const int maxm=1e6+5;
int n,m,deg[maxn],x,y,hd[maxn],cnt,limit,out[maxn];
bitset<maxn/2>vis[maxn];
long long ans;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
struct Edge{
    int nxt,to;
}edge[maxm];
void add(int u,int v){
    edge[++cnt].nxt=hd[u];
    edge[cnt].to=v;
    hd[u]=cnt;
    return ;
}
void topsort(int op){
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(!deg[i])q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=hd[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            vis[v]|=vis[u];
            if(!(--deg[v])){
                q.push(v);
            }
        }
    }
    return ;
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=m;i++){
        x=read();
        y=read();
        deg[x]++;
        add(y,x);
    }
    for(int i=1;i<=n;i++){
        ans-=deg[i]+1;
        out[i]=deg[i];
    }
    limit=n/2;
    for(int i=1;i<=limit;i++){
        vis[i][i]=1;
    }
    topsort(0);
    for(int i=1;i<=n;i++){
        ans+=vis[i].count();
//        cout<<vis[i].count()<<endl;
        vis[i].reset();
        deg[i]=out[i];
    }
//    vis.reset();
    for(int i=limit+1;i<=n;i++){
        vis[i][i-limit]=1;
    }
    topsort(1);
    for(int i=1;i<=n;i++){
//        cout<<vis[i].count()<<" ";
        ans+=vis[i].count();
    }
    cout<<ans;
    return 0;
}

/*
5 5
1 2
1 3
2 3
3 4
4 5
*/ 

---

B. 时间机器

说实话考场上没有认真看懂题，光用网络流水了一下居然拿到了70分

这道题正解贪心

考虑所有元件和节点按左端点第一关键字右端点第二关键字排序后，那么右端点靠左的元件越容易用不上，所以尽可能优先选取右端点靠左的元件

那么对于一个节点拥有一个左右端点满足条件的候选集合，考虑左端点对于后面的节点都是可用的，但是右端点可能会被淘汰掉，那么就选择右端点最靠左的一个元件进行匹配

这个可以用 \(set\) 实现

注意这道题一开始一直被卡常，后来发现 \(s.lower\_bound(xxx)\) 比 \(lower\_bound(s.begin(),s.end(),xxx)\) 快好多

代码实现

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int maxn=1e6+5;
int t,n,m,tp;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
struct Th{
    int l,r,num;
}a[maxn],b[maxn];
struct Node{
    int fi;
    mutable int se;
    Node(int x=0,int y=0):fi(x),se(y){}
};
bool operator < (const Node &x,const Node &y){
    return x.fi!=y.fi?x.fi<y.fi:x.se<y.se;
}
multiset<Node>s;
bool operator < (const Th &x,const Th &y){
    return x.l==y.l?x.r<y.r:x.l<y.l;
}
void solve(){
    tp=1;
    for(int i=1;i<=n;i++){
        while(tp<=m&&b[tp].l<=a[i].l){
            s.insert(Node(b[tp].r,b[tp].num));
            tp++;
        }
        while(a[i].num){
            multiset<Node>::iterator it=s.lower_bound(Node(a[i].r,0));
            if(it==s.end()){
                puts("No");
                return ;
            }
            if(a[i].num < it->se){
                it->se -= a[i].num;
                break;
            }
            a[i].num-= it->se;
            s.erase(it);
        }
    }
    puts("Yes");
}
signed main(){
    t=read();
    while(t--){
        n=read();
        m=read();
        for(int i=1;i<=n;i++){
            a[i].l=read();
            a[i].r=read();
            a[i].num=read();
        }
        for(int i=1;i<=m;i++){
            b[i].l=read();
            b[i].r=read();
            b[i].num=read();
        }
        sort(a+1,a+n+1);
        sort(b+1,b+m+1);
        s.clear();
        solve();
    }
    return 0;
}

/*
3
2 2
1 2 2
1 2 1
1 2 1
1 2 2
2 2
1 4 2
3 5 1
1 4 2
2 5 1

3 2
1 3 1
2 4 1
3 5 1
1 3 2
2 5 1

*/ 

---

C. weight

考完试 cyh 说和题单上的 Mst 这道题基本上是一样的，真后悔当时没看这道题

首先把最小生成树建出来，然后树边和非树边分别讨论

如果是非树边，那么答案为生成树上两端点路径上边权最大值 -1

如果是树边，则是所有和这条边有关的非树边的最小值 -1

可以采用树剖，每条非树边查询一次修改一次即可

cyh 的LCT理论复杂度少一个 \(log\)，也非常好维护

注意判不在连通块里的边（可以用并查集判断），树剖需要边化点，更新时不能选上面的那个点

于是一直调一直改写了将近300行……

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int maxm=4e5+5;
//const int inf=
int n,m,ans[maxn],x,y,w,op;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
namespace p2{
    int hd[maxn],cnt,cnt1,re[maxn],fa[maxn],tot,id[maxn],pa[maxn],siz[maxn],son[maxn],dep[maxn],tp[maxn],val[maxn];
    struct Edge{
        int nxt,to,val,id;
    }edge[maxm];
    void add(int u,int v,int w,int num){
        edge[++cnt].nxt=hd[u];
        edge[cnt].to=v;
        edge[cnt].val=w;
        edge[cnt].id=num;
        hd[u]=cnt;
        return ;
    }
    struct Ch{
        int from,to,id,val;
    }link[maxm];
    void make(int u,int v,int w,int num){
        link[++cnt1].to=v;
        link[cnt1].from=u;
        link[cnt1].val=w;
        link[cnt1].id=num;
        return ;
    }
    void dfs(int u){
//        cout<<u<<" "<<endl;
        siz[u]=1;
        for(int i=hd[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[u])continue;
            dep[v]=dep[u]+1;
            fa[v]=u;
            val[v]=edge[i].val;
            pa[v]=edge[i].id;
//            cout<<"hhh "<<v<<" "<<pa[v]<<endl;
            dfs(v);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]])son[u]=v;
        }
        return ;
    }
    void dfs1(int u,int top){
        tp[u]=top;
        id[u]=++tot;
        re[tot]=u;
//        cout<<u<<" ";
        if(son[u])dfs1(son[u],top);
        for(int i=hd[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[u]||v==son[u])continue;
            dfs1(v,v);
        }
        return ;
    }
    struct Seg{
        int l,r,mx,lazy;
    }t[maxn*4];
    void update(int p){
        t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
        return ;
    }
    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        t[p].lazy=0x3f3f3f3f;
        if(l==r){
            t[p].mx=val[re[l]];
//            cout<<"kkk "<<l<<" "<<val[id[l]]<<endl;
            return ;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        update(p);
        return ;
    }
    int ask(int p,int l,int r){
        if(l>r)return 0;
        if(t[p].l>=l&&t[p].r<=r)return t[p].mx;
        int mx=0;
        int mid=t[p].l+t[p].r>>1;
        if(l<=mid)mx=ask(p<<1,l,r);
        if(r>mid)mx=max(mx,ask(p<<1|1,l,r));
        return mx;
    }
    int ques(int x,int y){
        int mx=0;
//        cout<<"hhh "<<endl;
        while(tp[x]!=tp[y]){
            if(dep[tp[x]]<dep[tp[y]])swap(x,y);
//            cout<<"ppp "<<id[tp[x]]<<" "<<id[x]<<endl;
            mx=max(mx,ask(1,id[tp[x]],id[x]));
            x=fa[tp[x]];
        }
//        cout<<mx<<endl;
        if(dep[x]>dep[y])swap(x,y);
//        cout<<"ppp "<<id[x]+1<<" "<<id[y]<<endl;
        mx=max(mx,ask(1,id[x]+1,id[y]));
//        cout<<id[x]<<" "<<id[y]<<endl;
        return mx;
    }
    void ch(int p,int l,int r,int w){
        if(l>r)return ;
        if(t[p].l>=l&&t[p].r<=r){
            t[p].lazy=min(t[p].lazy,w);
            return ;
        }
        int mid=t[p].l+t[p].r>>1;
        if(l<=mid)ch(p<<1,l,r,w);
        if(r>mid)ch(p<<1|1,l,r,w);
        return ;
    }
    void change(int x,int y,int w){

        while(tp[x]!=tp[y]){
            if(dep[tp[x]]<dep[tp[y]])swap(x,y);

            ch(1,id[tp[x]],id[x],w);
            x=fa[tp[x]];
        }
//        cout<<mx<<endl;
        if(dep[x]>dep[y])swap(x,y);

        ch(1,id[x]+1,id[y],w);
        return ;
    }
    void spread(int p){
        if(t[p].l==t[p].r){
//            cout<<t[p].l<<" "<<re[t[p].l]<<" "<<pa[re[t[p].l]]<<endl;
            ans[pa[re[t[p].l]]]=t[p].lazy;
            return ;
        }
        t[p<<1].lazy=min(t[p<<1].lazy,t[p].lazy);
        t[p<<1|1].lazy=min(t[p<<1|1].lazy,t[p].lazy);
        spread(p<<1);
        spread(p<<1|1);
        return ;
    }
    void start(){
        dfs(1);
        pa[1]=m+1;
        dfs1(1,1);
        build(1,1,n);
//        for(int i=1;i<=n;i++){
//            cout<<pa[i]<<endl;
//        }
//        cout<<endl;
//        cout<<"hhh ";
        for(int i=1;i<=cnt1;i++){
            int x=link[i].from;
            int y=link[i].to;
//            cout<<link[i].id<<" "<<x<<" "<<y<<" "<<link[i].val<<endl;
            ans[link[i].id]=ques(x,y);
//            flag[link[i].id];
//            cout<<ans[link[i].id]<<endl;
//            cout<<link[i].id<<" "<<ans[link[i].id]<<endl;
            change(x,y,link[i].val);
        }
        spread(1);
        return ;
    }
}
namespace p1{
    int hd[maxn],cnt,fa[maxn];
    struct Edge{
        int nxt,to,from,val,id;
    }edge[maxm],edge1[maxm];
    void add(int u,int v,int w){
        edge[++cnt].nxt=hd[u];
        edge[cnt].to=v;
        edge[cnt].from=u;
        edge[cnt].val=w;
        return ;
    }
    bool cmp(Edge a,Edge b){
        return a.val<b.val;
    }
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void kruscal(){
        sort(edge+1,edge+m+1,cmp);
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        for(int i=1;i<=m;i++){
            int u=edge[i].from;
            int v=edge[i].to;
            x=find(u);
            y=find(v);
            if(x!=y){
                fa[x]=y;
//                cout<<u<<" "<<v<<" "<<edge[i].val<<" "<<edge[i].id<<endl;
                p2::add(u,v,edge[i].val,edge[i].id);
                p2::add(v,u,edge[i].val,edge[i].id);
            }
            else{
//                cout<<u<<" "<<v<<" "<<edge[i].val<<" "<<edge[i].id<<endl;
                p2::make(u,v,edge[i].val,edge[i].id);
            }
        }
        return ;
    }
}
namespace p3{
    int fa[maxn],tot,tot1,idx[maxn];
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void pd(){
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        for(int i=1;i<=m;i++){
            int x=p1::edge[i].from;
            int y=p1::edge[i].to;
            x=find(x);
            y=find(y);
            if(x!=y)fa[x]=y;
        }
        for(int i=1;i<=m;i++){
            p1::edge1[i]=p1::edge[i];
//            cout<<find(p1::edge[i].from)<<" "<<find(1)<<endl;
            if(find(p1::edge[i].from)!=find(1)&&find(p1::edge[i].to)!=find(1)){
                ans[p1::edge[i].id]=1;
//                cout<<"ppp "<<p1::edge[i].id<<endl;
                tot++;
            }
            else idx[++tot1]=i;
        }
        p1::cnt=0;
        memset(p1::hd,0,sizeof p1::hd);
        for(int i=1;i<=tot1;i++){
            p1::add(p1::edge1[idx[i]].from,p1::edge1[idx[i]].to,p1::edge1[idx[i]].val);
            p1::edge[p1::cnt].id=p1::edge1[idx[i]].id;
        }
        m=tot1;
    }
}
int main(){
//    freopen("c.in","r",stdin);
//    freopen("c.out","w",stdout);
    n=read();
    m=read();
    op=read();
    for(int i=1;i<=m;i++){
        x=read();
        y=read();
        w=read();
        p1::add(x,y,w);
        p1::edge[p1::cnt].id=i;
    }
//    cout<<"hhh ";
//    p3::tot1=m;
    p3::pd();
//    cout<<"ppp "<<m<<endl;
//    cout<<"hhh ";
//    for(int i=1;i<=m;i++){
//        cout<<p1::edge[i].from<<" "<<p1::edge[i].to<<" "<<p1::edge[i].val<<" "<<p1::edge[i].id<<endl;
//    }
    p1::kruscal();
//    cout<<"hhh ";
    p2::start();
    for(int i=1;i<=p3::tot+p3::tot1;i++){
        if(ans[i]==0x3f3f3f3f)printf("-1 ");
        else printf("%d ",ans[i]-1);
    }
    return 0;
}

/*
5 4 0
4 5 2
1 2 1
2 3 2
3 1 3

*/ 

\(\color{white}{\mathbb{困于心，衡于虑，而后作}}\)