#1192084 (C++17) No.3756 Udon Network

• 問題: No.3756 Udon Network
• ユーザー: Cafe1942
• 提出日時: 2026-10-09 20:06:08
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 946 ms / 2,000 ms
• コード長: 4,624 bytes
• コンパイル時間: 1,050 ms
• コンパイル使用メモリ: 170,004 KB
• 実行使用メモリ: 106,268 KB
• 最終ジャッジ日時: 2026-10-09 20:06:44
• 合計ジャッジ時間: 29,514 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

サブタスク	配点	結果
Example	0 %	AC * 8
Subtask $1$	2 %	AC * 15
Subtask $2$	4 %	AC * 22
Subtask $3$	8 %	AC * 9
Subtask $4$	16 %	AC * 10
Subtask $5$	32 %	AC * 10
Subtask $6$	38 %	AC * 53
合計	4 * 100% = 400 点

ソースコード

#include <iostream>
//#define RANDOMTEST_DEBUG
#include <iomanip>//小数点出力用
//cout << fixed << setprecision(10) << ans;
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
using ll = long long;
using namespace std;
#define modPHash 1909826258152820093LL
#define modP (ll)998244353
bool chkrng0idx(ll pos, ll sup) { return (0 <= pos && pos < sup); }
ll clk4(ll num) { return (num - 2) * (num % 2); }
void yn(bool tf) { cout << (tf ? "Yes\n" : "No\n"); }
using namespace std;

#define MAX_V 200002
int Parent[MAX_V];
int Parent2[MAX_V];
set<int> SS[MAX_V];

vector<pair<int, int>>QS;
set<pair<int, int>> QQ[MAX_V];
int cur;
vector<int>ans;

void init() {
    for (int i = 0;i < MAX_V;i++) {
        Parent[i] = -1;
        Parent2[i] = -1;
    }
}

int find(int x) {
    if (Parent[x] == -1) {
        return x;
    }
    else {
        Parent[x] = find(Parent[x]);
        return Parent[x];
    }
}
int find2(int x) {
    if (Parent2[x] == -1) {
        return x;
    }
    else {
        Parent2[x] = find2(Parent2[x]);
        return Parent2[x];
    }
}

void unite(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a != b) {
        if (SS[a].size() < SS[b].size()) {
            for (auto itr = SS[a].begin();itr != SS[a].end(); itr++) {
                SS[b].insert(*itr);
            }
            Parent[a] = b;
        }
        else {
            for (auto itr = SS[b].begin();itr != SS[b].end(); itr++) {
                SS[a].insert(*itr);
            }
            Parent[b] = a;
        }
    }

    a = find2(x);
    b = find2(y);
    if (a != b) {
        if (QQ[a].size() < QQ[b].size()) {
            for (auto itr = QQ[a].begin();itr != QQ[a].end(); itr++) {
                QQ[b].insert(*itr);
            }
            Parent2[a] = b;
            while (QQ[b].size()) {
                auto X = (*QQ[b].begin());
                if (X.first <= SS[find(QS[X.second].first)].size()) {
                    ans[X.second] = cur;
                    QQ[b].erase(QQ[b].begin());
                }
                else {
                    break;
                }
            }
        }
        else {
            for (auto itr = QQ[b].begin();itr != QQ[b].end(); itr++) {
                QQ[a].insert(*itr);
            }
            Parent2[b] = a;
            while (QQ[a].size()) {
                auto X = (*QQ[a].begin());
                if (X.first <= SS[find(QS[X.second].first)].size()) {
                    ans[X.second] = cur;
                    QQ[a].erase(QQ[a].begin());
                }
                else {
                    break;
                }
            }
        }
    }

}

void solve() {
    int N, M, Q;
    cin >> N >> M >> Q;
    map<int, int>comp;
    vector<int>A(N);
    for (int i = 0;i < N;i++) {
        cin >> A[i];
        SS[i].insert(A[i]);
    }
    vector<pair<int, pair<int, int>>>E(M);
    for (int i = 0;i < M;i++) {
        cin >> E[i].second.first >> E[i].second.second >> E[i].first;
        comp[E[i].first] = -1;
        E[i].second.first--;
        E[i].second.second--;
    }
    int cc = 0;
    vector<int>inv(comp.size() + 1);
    for (auto itr = comp.begin();itr != comp.end();itr++) {
        (*itr).second = cc;
        inv[cc] = (*itr).first;
        cc++;
    }
    for (int i = 0;i < M;i++) {
        E[i].first = comp[E[i].first];
    }
    inv[comp.size()] = -1;
    sort(E.begin(), E.end());
    QS = vector<pair<int, int>>(Q);
    ans = vector<int>(Q, comp.size());
    for (int i = 0;i < Q;i++) {
        cin >> QS[i].first >> QS[i].second;
        QS[i].first--;
        if (QS[i].second == 1) {
            ans[i] = -1;
        }
        else {
            QQ[QS[i].first].insert({ QS[i].second , i });
        }
    }
    init();
    int p = 0;
    cur = 0;
    for (p = 0;p < M;cur++) {
        while (p < M && E[p].first <= cur) {
            unite(E[p].second.first, E[p].second.second);
            p++;
        }
    }
    for (int i = 0;i < Q;i++) {
        if (ans[i] >= 0) {
            ans[i] = inv[ans[i]];
        }
        else {
            ans[i] = 0;
        }
        cout << ans[i] << "\n";
    }
    return;
}

#ifdef RANDOMTEST_DEBUG
void solve_Brute_Force() {
    return;
}
#endif

int main() {
#ifdef RANDOMTEST_DEBUG
    int TESTCASES = 100;
    while (TESTCASES--) {
        solve();
        solve_Brute_Force();
        cout << endl;
    }
#else
    int TESTCASES = 1;
    //cin >> TESTCASES;
    while (TESTCASES--) {
        solve();
    }
#endif
    return 0;
}