Submission #1358288

#TimeUsernameProblemLanguageResultExecution timeMemory
1358288neckto12Mi Teleférico (JOI25_ho_t3)C++20
0 / 100
2096 ms44488 KiB
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define db double
int mod = 1e9 + 7;
mt19937 rd(20);
void solve();

int32_t main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#endif
    int tt = 1; //cin >> tt;
    while (tt--) solve();
    return 0;
}

struct DSU {
    vector<int> dsu;
    vector<int> sz;
    DSU(int n) {
        dsu.assign(n, 0);
        sz.assign(n, 1);
        for (int i = 0; i < n; ++i) dsu[i] = i;
    }
    int get(int x) {
        if (dsu[x] == x) return x;
        return dsu[x] = get(dsu[x]);
    }
    void merge(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) return;
        if (sz[a] > sz[b]) swap(a, b);
        dsu[a] = b;
        sz[b] += sz[a];
    }
    bool is(int a, int b) {
        return get(a) == get(b);
    }
};
void solve() {
    int n, m, p;
    cin >> n >> m >> p;
    vector<vector<vector<int>>> g(n);
    vector<int> nums;
    vector<vector<int>> rr;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        nums.push_back(c);
        g[a].push_back({b, c});
        rr.push_back({a, b, c});
    }
    sort(rr.begin(), rr.end(), [](auto a, auto b){return a[2] < b[2];});
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    vector<vector<int>> b;
    int in = 0;
    m = rr.size();
    for (int i = 0; i < nums.size(); ++i) {
        DSU dsu(n);
        while (in < m && rr[in][2] < nums[i]) in++;
        if (in == m) continue;
        for (int j = in; j < m; ++j) {
            dsu.merge(rr[j][0], rr[j][1]);
            if (dsu.is(0, n - 1)) {
                b.push_back({nums[i], rr[j][2]});
                break;
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        bool f = false;
        for (auto &i : b) {
            if (max((int)0, l - i[0]) + max((int)0, i[1] - r) <= x) {
                cout << "Yes\n";
                f = true;
                break;
            }
        }
        if (f) continue;
        cout << "No\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...