不懂就问
查看原帖
不懂就问
1000298
Vsinger_洛天依楼主2024/3/6 19:45

为啥WA了

#include<bits/stdc++.h>
using namespace std ; 
inline void fire(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);}
namespace Fread{const int SIZE=(1<<18);char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}}
namespace Fwrite{const int SIZE=(1<<18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout),S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR(){flush();}}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){char c=getchar();bool f=false;while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}Reader&operator>>(double & x){char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}template<class _Tp>Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}template<class _Tp,class _tp>Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}Reader(){}}cin;struct Writer{static const int set_precision = 6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(string str){int fir=0,ed=str.size();while(fir<ed) putchar(str[fir++]);return *this;}template<class _Tp>Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}template<class _Tp,class _tp>Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}Writer(){}}cout;}
#define FastI  Fastio::cin
#define FastO  Fastio::cout
#define ull unsigned long long
#define int long long
#define INF (0x66ccff0712ll)
#define N (0x66ccff)
#define maxn (2000010)
#define MAXN (int)(1e6+5)
#define MAXM (int)(1e5+5)
#define re register
#define lower_bound std::lower_bound
#define upper_bound std::upper_bound
#define unique std::unique
#define string std::string
#define pair std::pair
#define vector std::vector
#define map std::map
#define set std::set
#define queue std::queue
#define make_pair std::make_pair
#define priority_queue std::priority_queue
#define bitset std::bitset
#define deque std::deque
#define array std::array
#define unordered_set std::unordered_set
#define unordered_map std::unordered_map
#define list std::list
#define it map<int,int>::iterator
#define endl "\n"
#define PII pair<int,int>
#define swap std::swap 
#define mid ((l+r)>>1)
#define lc son[x][0]
#define rc son[x][1]
int n,m,q,k;
struct HS_xh{
    int k,a,b,num;
};
vector<HS_xh> vec;
bool dis[N];
struct node{
    int s,son,val;
}T[N];
inline bool cmp(node a, node b){
    return a.val<b.val;
} 
map<pair<int,int>,int> mapp;
int fa[N],son[N][2],val[N],ans[N],st[N],lazy_reverse[N];
bool rev[N];
inline bool isroot(int x){
	return ((son[fa[x]][0]==x)||(son[fa[x]][1]==x));
}
inline void pushup(int x){
    ans[x]=val[x];
    if(T[ans[lc]].val>T[ans[x]].val)
        ans[x]=ans[lc];
    if(T[ans[rc]].val>T[ans[x]].val)
        ans[x]=ans[rc];
}
inline void reserve(int x){
    swap(lc,rc);
	rev[x]^=1;
}
inline void pushdown(int x){
	if(rev[x]){
		if(lc)reserve(lc);
		if(rc)reserve(rc);
		rev[x]=0;
	}
}
inline void rotate(int x){
	int y=fa[x],z=fa[y],k=son[y][1]==x,w=son[x][!k];
	if(isroot(y))
        son[z][son[z][1]==y]=x;
    son[x][!k]=y;
	son[y][k]=w;
	if(w)
        fa[w]=y;
    fa[y]=x;fa[x]=z;
	pushup(y);
}
inline void splay(int x){
	int y=x,z=0;
	st[++z]=y;
	while(isroot(y))
        st[++z]=y=fa[y];
	while(z)
        pushdown(st[z--]);
	while(isroot(x)){
		y=fa[x],z=fa[y];
		if(isroot(y))
			rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
		rotate(x);
	}
	pushup(x);
}
inline void access(int x){
	for(int y=0;x;x=fa[y=x]){
		splay(x);
		rc=y;
        pushup(x);
    }
}
inline void toroot(int x){
	access(x);
	splay(x);
	reserve(x);
}
inline int Find(int x){
	access(x);
	splay(x);
	while(lc){
        pushdown(x);
        x=lc;
    }
    splay(x);
	return x;
}
inline void split(int x,int y){
	toroot(x);
	access(y);
    splay(y);
}
inline void link(int x,int y){
	toroot(x);
    fa[x]=y;
}
inline void cut(int x, int y){
    split(x,y); 
    fa[x]=son[y][0]=0;
}
void add(int const& x, int const& y) {
    fa[x]=lc=rc=rev[x]=0;
    val[x]=ans[x]=y;
}
void kur(){
    int cnt=0;
    for(int i=1;i<=m;++i)
        if(!dis[i]){
            if(cnt==n-1) break;
            if(Find(T[i].s)==Find(T[i].son)) continue;
            link(T[i].s,i+n),link(T[i].son,i+n);
            ++cnt;
        }
}
void pre(){
    sort(T+1,T+1+m,cmp);
    for(int i=1;i<=m;++i) 
        mapp[make_pair(T[i].s,T[i].son)]=i;
    for(int i=1;i<=q;++i){
        HS_xh qwq;
        FastI>>qwq.k>>qwq.a>>qwq.b;
        if(qwq.a>qwq.b) 
            swap(qwq.a,qwq.b);
        if(qwq.k==2){
            qwq.num=mapp[make_pair(qwq.a,qwq.b)]; 
            dis[qwq.num]=1;
        }
        else qwq.num=0;
        vec.push_back(qwq);
    }
    T[0].val=0;
    for(int i=1;i<=n;++i) 
        add(i,(i>n)?(i-n):(0));
    kur();
}
signed main(){
    FastI>>n>>m>>q;
    for(int i=1;i<=m;++i){
        FastI>>T[i].s>>T[i].son>>T[i].val;
        if(T[i].s>T[i].son) swap(T[i].s,T[i].son);
    }
    pre();
    stack<int>sta;
    for(int i=q-1;i>=0;--i){
        int x=vec[i].a,y=vec[i].b;
        split(x,y);
        if(vec[i].k==1){
            sta.push(T[ans[y]].val);
        }
        else{ 
            int num=vec[i].num,j=ans[y];
            if(T[num].val<T[j].val){
                cut(T[j].s,j+n);
                cut(j+n,T[j].son);
                link(x,num+n);
                link(num+n,y);
            }
        }
    }
    while(!sta.empty()){
        FastO<<sta.top()<<endl;
        sta.pop();
    }
}
2024/3/6 19:45
加载中...