QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662281 | #7524. A Challenge For a Tourist | ucup-team3519 | WA | 0ms | 23908kb | C++17 | 5.4kb | 2024-10-20 22:32:44 | 2024-10-20 22:32:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
//const int MN = 2e5 + 20;
const int INF = 2e9 + 1000;
const LL INFLL = 8e18 + 1000;
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
//模板区域~~~~~~~
struct Basis{
static const int N = 30;
array<int, N> base;
int cnt = 0;
bool add(int x){
for(int i = N - 1; i >= 0; i--){
if((x >> i & 1) == 0) continue;
if(base[i]) x ^= base[i];
else {
base[i] = x;
cnt++;
return 1;
}
}
return 0;
}
int querymin(int x){
for(int i = N - 1; i >= 0; i--){
x = min(x, x ^ base[i]);
}
return x;
}
bool hav(int x) {
return querymin(x) == 0;
}
Basis operator += (Basis o) {
for(auto x : o.base) this->add(x);
return *this;
}
int size(){
return cnt;
}
};
const int N = 4e5 + 10;
namespace hdl {
V<int> e[N];
int dep[N], f[N], sz[N], hs[N], top[N];
int l[N], r[N], id[N], tot;
void dfs1(int x, int p) {
dep[x] = dep[p] + 1, f[x] = p, sz[x] = 1, hs[x] = -1;
for(auto y : e[x]) {
if(y == p) continue;
dfs1(y, x);
sz[x] += sz[y];
if(hs[x] == -1 || sz[y] > sz[hs[x]]) hs[x] = y;
}
}
void dfs2(int x, int t) {
top[x] = t, l[x] = ++tot, id[l[x]] = x;
if(hs[x] != -1) {
dfs2(hs[x], t);
}
for(auto y : e[x]) {
if(y == f[x] || y == hs[x]) continue;
dfs2(y, y);
}
r[x] = tot;
}
void build(int n){
tot = 0;
for(int i = n; i >= 1; i--) {
if(!l[i]) {
dfs1(i, 0);
dfs2(i, i);
}
}
}
int LCA(int a,int b) {
while(top[a] != top[b]) {
if(dep[top[a]] > dep[top[b]]) a = f[top[a]];
else b = f[top[b]];
}
return (dep[a] > dep[b] ? b : a);
}
}
namespace dsu {
int f[N], siz[N];
int par(int x){
if(x == f[x]) return x;
return f[x] = par(f[x]);
}
void mer(int a, int b){
a = par(a), b = par(b);
if(a == b) return;
f[a] = b;
siz[b] += siz[a];
}
void ini(int n) {
for(int i = 1; i <= n; i++) f[i] = i, siz[i] = 1;
}
}
void solve() {
int n, m; cin >> n >> m;
V<array<int, 3>> E(m + 1);
V<int> ini_dif(m + 1);
for(int i = 1; i <= m; i++) {
auto &[x, y, z] = E[i];
cin >> x >> y >> z;
ini_dif[i] = z;
}
sort(all1(E), [&](array<int, 3> a, array<int, 3> b) {
return a[2] < b[2];
});
int q; cin >> q;
V<array<int, 3>> ask(q + 1);
V<int> ans(q + 1);
for(int i = 1; i <= q; i++) {
auto &[x, y, z] = ask[i];
cin >> x >> y >> z;
}
V<int> xordep(n + 1);
{ //cal xordep
V<int> vis(n + 1);
V<V<pi>> e(n + 1);
dsu::ini(n);
for(int i = 1; i <= m; i++) {
auto [x, y, w] = E[i];
if(dsu::par(x) == dsu::par(y)) continue;
dsu::mer(x, y);
e[x].pb({y, w}), e[y].pb({x, w});
}
auto dfs = [&](int x, int p, auto dfs) -> void {
vis[x] = 1;
for(auto [y, w] : e[x]) if(y != p) {
xordep[y] = xordep[x] ^ w;
dfs(y, x, dfs);
}
};
for(int i = 1; i <= n; i++) {
if(!vis[i]) dfs(i, 0, dfs);
}
}
for(int i = 1; i <= q; i++) {
auto &[x, y, h] = ask[i];
h ^= xordep[x] ^ xordep[y];
}
for(int i = 1; i <= m; i++) {
auto &[x, y, cyc] = E[i];
cyc ^= xordep[x] ^ xordep[y];
}
dsu::ini(n + m);
int tot = n;
V<Basis> bas(n + m + 1);
V<int> dif(n + m + 1);
for(int i = 1; i <= m; i++) {
auto [x, y, cyc] = E[i];
++tot;
int px = dsu::par(x), py = dsu::par(y);
hdl::e[tot].pb(px);
if(py != px) hdl::e[tot].pb(py);
dsu::f[px] = dsu::f[py] = tot;
bas[tot].add(cyc);
bas[tot] += bas[px];
bas[tot] += bas[py];
dif[tot] = ini_dif[i];
}
hdl::build(n + m);
dsu::ini(n + m);
for(int i = 1; i <= tot; i++) {
if(hdl::f[i] && bas[hdl::f[i]].size() == bas[i].size()) {
dsu::mer(i, hdl::f[i]);
}
}
for(int i = 1; i <= q; i++) {
auto [a, b, h] = ask[i];
int lca = hdl::LCA(a, b);
if(!lca) {
ans[i] = -1;
continue;
}
int x = lca;
while(x && !bas[x].hav(h)) x = hdl::f[dsu::par(x)];
if(x) {
ans[i] = dif[x];
} else ans[i] = -1;
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 23908kb
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 1 4
result:
wrong answer 2nd numbers differ - expected: '2', found: '1'