QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662281#7524. A Challenge For a Touristucup-team3519WA 0ms23908kbC++175.4kb2024-10-20 22:32:442024-10-20 22:32:46

Judging History

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

  • [2024-10-20 22:32:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:23908kb
  • [2024-10-20 22:32:44]
  • 提交

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();
}

詳細信息

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'