T2 attack 题解

将病毒按攻击力从小到大排序，网线也从小到大排序，一个病毒能入侵的网络比它强的病毒也能入侵，如果病毒攻击力递增，下一个病毒可入侵网络在此基础上扩展即可，每个节点只扩展一次,不会撤销，每次将病毒可入侵的边加入，用并查集维护连通块の利润和，最高重要度及其个数，并统计这次入侵的连通块，注意判重。然后，50分就有了？！

此题卡常数，需要一个给力的输入输出优化

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
#define BUFSIZE 300000
namespace fib {char b[BUFSIZE]={},*f=b;}
#define gc ((*fib::f)?(*(fib::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
void read(int &tmp) {
    tmp=0; bool fu=0; char s;
    while(s=gc,s!='-'&&(s<'0'||s>'9')) ;
    if(s=='-') fu=1; else tmp=s-'0';
    while(s=gc,s>='0'&&s<='9') tmp=tmp*10+s-'0';
    if(fu) tmp =  -tmp; 
}
void read(LL &tmp) {
    tmp=0; bool fu=0; char s;
    while(s=gc,s!='-'&&(s<'0'||s>'9')) ;
    if(s=='-') fu=1; else tmp=s-'0';
    while(s=gc,s>='0'&&s<='9') tmp=tmp*10+s-'0';
    if(fu) tmp =  -tmp; 
}
namespace fob {char b[BUFSIZE]={},*f=b,*g=b+BUFSIZE-2;}
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
struct foce {~foce() {pob; fflush(stdout);}} _foce;
namespace ib {char b[100];}
inline void pint(LL x) {
    if(x==0) {pc(48); return;}
    if(x<0) {pc('-'); x=-x;}
    char *s=ib::b;
    while(x) *(++s)=x%10, x/=10;
    while(s!=ib::b) pc((*(s--))+48);
}
#define N 410000
struct E {int to,next;}g[3010000];
int fr[N],tot;
void Add(int from,int to) {
    g[++tot].to = to;
    g[tot].next = fr[from];
    fr[from] = tot;
}
int n,m,q,num[N],val[N],rk[N],rke[N],x[N],y[N],v[N];
int f[N];
LL ans1[N],ans2[N],hs[N],ha[N],b[N];
inline bool cmp(const int &a,const int &b) {return val[a] < val[b];}
inline bool cmpe(const int &a,const int &b) {return v[a] < v[b];}
inline int fd(int x) {
    return f[x]==x ? x : f[x]=fd(f[x]);
}
inline void Mer(int x,int y) {
    x = fd(x); y = fd(y);
    if(x != y) {
        f[x] = y;
        b[y] += b[x];
        if(ha[y] == ha[x]) hs[y] += hs[x];
        else if(ha[y] < ha[x]) hs[y] = hs[x],ha[y] = ha[x];
    }
}
int le = 1;bool done[N];
inline void slove(int t) {
    LL tp1 = 0,tp2 = 0,hha = 0;
    while(le <= m && v[rke[le]] <= val[t]) {Mer(x[rke[le]],y[rke[le]]);le++;}
    for (int i = fr[t]; i; i = g[i].next) {
     int po = fd(g[i].to);
     if (!done[po]) {
        done[po] = 1;
        if(ha[po] > hha) tp1 = ha[po]*hs[po],hha = ha[po];
        else if(ha[po] == hha) tp1 += ha[po]*hs[po];
        tp2 += b[po];   
     }
    }
    for (int i = fr[t]; i; i = g[i].next) done[fd(g[i].to)] = 0;
    ans1[t] = tp1; ans2[t] = tp2;
}
int main() {
    freopen("attack.in","r",stdin);freopen("attack.out","w",stdout);
    read(n); read(m); read(q); LL totb = 0;
    for (int i = 1; i <= n; i++) read(ha[i]),f[i] = i,hs[i] = 1;;
    for (int i = 1; i <= n; i++) read(b[i]),totb += b[i];
    for (int i = 1; i <= m; i++) read(x[i]),read(y[i]),read(v[i]),rke[i] = i;;
    for (int i = 1; i <= q; i++) {
        read(num[i]),read(val[i]);rk[i] = i;
        for (int j = 1,tp; j <= num[i]; j++) {
            read(tp);
            Add(i,tp);
        } 
    }
    sort(rk+1,rk+q+1,cmp); sort(rke+1,rke+m+1,cmpe);
    for (int i = 1; i <= q; i++) slove(rk[i]); 
    for (int i = 1; i <= q; i++) pint(ans1[i]),pc(' '),pint(totb-ans2[i]),pc('\n');
    return 0;
}