#1186716 (C++23) No.3756 Udon Network

• 問題: No.3756 Udon Network
• ユーザー: Jikky1618
• 提出日時: 2026-09-13 18:36:58
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: RE
• 実行時間: -
• コード長: 3,583 bytes
• コンパイル時間: 2,308 ms
• コンパイル使用メモリ: 365,664 KB
• 実行使用メモリ: 32,860 KB
• 最終ジャッジ日時: 2026-10-09 17:45:26
• 合計ジャッジ時間: 18,967 ms
• ジャッジサーバーID （参考情報）: judge5_1 / judge4_0

サブタスク	配点	結果
Example	0 %	AC * 1 RE * 7
Subtask $1$	2 %	AC * 2 RE * 13
Subtask $2$	4 %	AC * 2 RE * 20
Subtask $3$	8 %	AC * 2 RE * 7
Subtask $4$	16 %	AC * 10
Subtask $5$	32 %	AC * 2 RE * 8
Subtask $6$	38 %	AC * 10 RE * 43
合計	4 * 16% = 64 点

ソースコード

// [Upsolve] c <= 2 のもとで O(M log M + N + Q)
// 2 つデータ持てばマージテクできますよね...そうですよね...

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#include <misc.hpp>
#else
#define debug(...)
#endif

struct UnionFind {
    int n, counter;
    vector<int> data;
    UnionFind(int size) : n(size), counter(size), data(size, -1) {}
    int root(int x) { return (data[x] < 0 ? x : data[x] = root(data[x])); }
    bool same(int x, int y) { return root(x) == root(y); }
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (-data[x] < -data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        counter--;
        return true;
    }
    int size(int x) { return -data[root(x)]; }
    int size() { return counter; }
    vector<int> group(int x) {
        vector<int> res;
        for (int i = 0; i < n; i++)
            if (same(x, i)) res.emplace_back(i);
        return res;
    }
    vector<vector<int>> groups() {
        vector<vector<int>> res(n);
        for (int i = 0; i < n; i++) res[root(i)].emplace_back(i);
        res.erase(remove_if(res.begin(), res.end(), [&](const vector<int>& v) { return v.empty(); }), res.end());
        return res;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i], A[i]--;
    vector<tuple<int, int, int>> E;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w, u--, v--;
        E.emplace_back(w, u, v);
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    ranges::sort(E);

    UnionFind uf(N);
    // k[i] := 店 i が含まれるグループの系列 (複数あるなら -1)
    vector<int> k(A);
    // dat[i] := root が i の答えが決まっていない店の集合
    vector<vector<int>> dat(N);
    for (int i = 0; i < N; i++) dat[i].emplace_back(i);
    constexpr int INF = (1 << 30) - 1;
    // ans[i] := 店 i から到達できる別系列の店で最小の巡礼度
    vector<int> ans(N, INF);
    for (auto [w, u, v] : E) {
        u = uf.root(u), v = uf.root(v);
        if (uf.same(u, v)) continue;
        if (k[u] == -1 && k[v] == -1) continue;  // 両方複数の系列を持つ
        if (uf.size(u) < uf.size(v)) swap(u, v);
        if (k[u] != -1 && k[v] == -1) {
            // u 側を確定
            for (auto x : dat[u]) ans[x] = w;
            dat[u].clear();
            k[u] = -1;
        }
        if (k[u] == -1 && k[v] != -1) {
            // v 側を確定
            for (auto x : dat[v]) ans[x] = w;
            dat[v].clear();
            k[v] = -1;
        }
        if (k[u] != -1 && k[v] != -1 && k[u] != k[v]) {
            // u, v 両方を確定
            for (auto x : dat[u]) ans[x] = w;
            for (auto x : dat[v]) ans[x] = w;
            dat[u].clear();
            dat[v].clear();
            k[u] = k[v] = -1;
        }
        uf.merge(u, v);
        // u, v を merge (併合した後の根は必ず u)
        for (auto x : dat[v]) dat[u].emplace_back(x);
        dat[v].clear();
    }
    auto solve = [&](int s, int c) -> int {
        if (c == 1) return 0;
        return ans[s] == INF ? -1 : ans[s];
    };

    while (Q--) {
        int s, c;
        cin >> s >> c, s--;
        assert(c <= 2);
        cout << solve(s, c) << "\n";
    }
}