QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372189#7524. A Challenge For a TouristRobeZH#WA 1ms3832kbC++234.4kb2024-03-31 03:17:422024-03-31 03:17:43

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 03:17:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3832kb
  • [2024-03-31 03:17:42]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
// #include<atcoder/all>
#define FR(i,n) for(int i=0;i<n;++i)
#define eb emplace_back
#define st first
#define nd second
#define x1 fxxkcjb
#define y1 fxxkyzc
#define x2 fxxkzzy
#define y2 fxxknitit
using namespace std;
namespace R=ranges;
template<typename T>
using func=function<T>;
template<typename T>
using vec=vector<T>;
using ll=long long;
using ld=long double;
using i128=__int128;
using pii=pair<int,int>;
const int mod=998244353;
struct E{
    int u,v,w;
};
int getbig(int x){
    assert(x>0);
    return 1<<(31-countl_zero(unsigned(x)));
}
struct GS{
    vector<int>bs;
    int clr(int val){
        for(int b:bs)if(val&getbig(b))val^=b;
        return val;
    }
    int add(int val){
        val=clr(val);
        if(!val)return val;
        for(int&b:bs)if(b^getbig(val))b^=val;//not needed, but is cleaner
        bs.eb(val);
        return val;
    }
};
struct SETS{
    unordered_set<int>a1,a2;
    void add(int x){
        if(a1.contains(x))a2.emplace(x),a1.erase(x);
        else a1.emplace(x);
    }
    void merge(SETS&s){
        for(int x:s.a1)add(x);
        for(int x:s.a2)a2.emplace(x);
    }
};
void sol(){
    int n,m;cin>>n>>m;
    vector<E>a(m);
    for(E&e:a)cin>>e.u>>e.v>>e.w,--e.u,--e.v;
    R::sort(a,[](E a,E b){return a.w<b.w;});
    vector<int>fa(n,-1),hsh(n,0);
    vector<GS>gss(n);
    vector<SETS>ques(n);
    func<int(int)>f=[&](int x){
        if(fa[x]==-1)return x;
        int nxt=fa[x];
        fa[x]=f(fa[x]);
        hsh[x]^=hsh[nxt];
        return fa[x];
    };
    int Q;cin>>Q;
    vector<int>orix(Q),oriy(Q),h(Q),ans(Q,-1);
    FR(i,Q){
        int x,y,z;cin>>x>>y>>z,--x,--y;
        ques[x].add(i);ques[y].add(i);
        orix[i]=x,oriy[i]=y,h[i]=z;
    }
    for(E e:a){
        int x=f(e.u),y=f(e.v);
        int neww=e.w^hsh[e.u]^hsh[e.v];
        if(x==y){
            if(int val=gss[x].add(neww)){
                // cerr<<val<<endl;
                vector<int>rmov;
                int bg=getbig(val);
                // cerr<<bg<<"b"<<endl;
                for(int q:ques[x].a2){
                    // cerr<<'h'<<q<<" "<<h[q]<<endl;
                    if(h[q]&bg){
                        h[q]^=val;
                        if(!h[q]){
                            ans[q]=e.w;
                            rmov.eb(q);
                        }
                    }
                }
                for(int q:rmov)ques[x].a2.erase(q);
            }
        }else{
            fa[x]=y;
            hsh[x]=neww;
            //merge gss
            auto sidework=[&](int x,int y){
                vector<int>tmp;
                for(int val:gss[x].bs)
                    if(int nv=gss[y].add(val))
                        tmp.eb(nv);
                if(!tmp.empty()){
                    for(int val:tmp){                 
                        vector<int>rmov;
                        int bg=getbig(val);
                        for(int q:ques[y].a2){
                            if(h[q]&bg){
                                h[q]^=val;
                                if(!h[q]){
                                    ans[q]=e.w;
                                    rmov.eb(q);
                                }
                            }
                        }
                        for(int q:rmov)ques[y].a2.erase(q);
                    }
                }
            };
            sidework(x,y);sidework(y,x);
            if(ques[y].a1.size()<ques[x].a1.size())swap(ques[y].a1,ques[x].a1);
            if(ques[y].a2.size()<ques[x].a2.size())swap(ques[y].a2,ques[x].a2);
            for(int q:ques[x].a1)if(ques[y].a1.contains(q)){
                f(orix[q]);f(oriy[q]);
                h[q]^=hsh[orix[q]]^hsh[oriy[q]];
                h[q]=gss[y].clr(h[q]);
                if(!h[q]){
                    ans[q]=e.w;
                }else{
                    ques[y].a2.emplace(q);
                }
            }else ques[y].a1.emplace(q);
            for(int q:ques[x].a2)ques[y].a2.emplace(q);
            //check ques e2
            //merge ques
        }
    }
    FR(i,Q)cout<<ans[i]<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    sol();
    return 0;
}
/*
6 6
5 6 3
6 2 2
1 2 1
2 3 2
2 4 3
4 5 4
3
1 3 1
1 3 3
1 3 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

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

output:

-1
2
4

result:

ok 3 number(s): "-1 2 4"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

2 1
1 2 1
1
1 2 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3580kb

input:

5 10
1 2 4
2 2 0
1 1 7
2 1 7
4 1 1
5 5 1
4 1 4
5 2 6
1 1 2
2 4 7
10
1 4 3
1 2 5
3 2 1
3 5 5
2 4 0
3 2 0
2 1 2
2 3 6
5 1 7
2 3 3

output:

2
6
-1
-1
4
-1
6
-1
7
-1

result:

wrong answer 9th numbers differ - expected: '6', found: '7'