QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372189 | #7524. A Challenge For a Tourist | RobeZH# | WA | 1ms | 3832kb | C++23 | 4.4kb | 2024-03-31 03:17:42 | 2024-03-31 03:17:43 |
Judging History
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'