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

• 問題: No.3756 Udon Network
• ユーザー: Cafe1942
• 提出日時: 2026-10-09 19:37:28
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,897 bytes
• コンパイル時間: 1,039 ms
• コンパイル使用メモリ: 168,480 KB
• 実行使用メモリ: 64,548 KB
• 最終ジャッジ日時: 2026-10-09 19:38:19
• 合計ジャッジ時間: 16,242 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge3_0

サブタスク	配点	結果
Example	0 %	AC * 8
Subtask $1$	2 %	AC * 15
Subtask $2$	4 %	AC * 22
Subtask $3$	8 %	AC * 3 TLE * 3 -- * 3
Subtask $4$	16 %	AC * 2 -- * 8
Subtask $5$	32 %	AC * 3 -- * 7
Subtask $6$	38 %	AC * 22 TLE * 3 -- * 28
合計	4 * 6% = 24 点

ソースコード

#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];
set<int> SS[MAX_V];

void init(vector<int> &A) {
    for (int i = 0;i < A.size();i++) {
        Parent[i] = -1;
        SS[i].clear();
        SS[i].insert(A[i]);
    }
}

int find(int x) {
    if (Parent[x] == -1) {
        return x;
    }
    else {
        Parent[x] = find(Parent[x]);
        return Parent[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;
        }
    }
}

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];
    }
    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());
    vector<pair<int, int>>QS(Q);
    vector<int>top(Q, comp.size()), bot(Q, -1);
    for (int i = 0;i < Q;i++) {
        cin >> QS[i].first >> QS[i].second;
        QS[i].first--;
        if (QS[i].second == 1) {
            top[i] = -1;
        }
    }
    while (1) {
        vector<pair<int, int>>mids;
        for (int i = 0;i < Q;i++) {
            if (top[i] - bot[i] > 1) {
                mids.push_back({ (top[i] + bot[i]) / 2, i });
            }
        }
        if (mids.size() == 0)break;
        sort(mids.begin(), mids.end());
        init(A);
        int p = 0;
        int pm = 0;
        int 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++;
            }
            while (pm < mids.size() && mids[pm].first == cur) {
                if (SS[find(QS[mids[pm].second].first)].size() >= QS[mids[pm].second].second) {
                    top[mids[pm].second] = cur;
                }
                else {
                    bot[mids[pm].second] = cur;
                }
                pm++;
            }
        }
    }
    for (int i = 0;i < Q;i++) {
        if (top[i] >= 0) {
            top[i] = inv[top[i]];
        }
        else {
            top[i] = 0;
        }
        cout << top[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;
}