Submission #1269224

#TimeUsernameProblemLanguageResultExecution timeMemory
1269224minhphu2907Drivers (BOI24_drivers)C++20
100 / 100
110 ms9912 KiB
#include <bits/stdc++.h>
using namespace std;
#define task ""
const int N = 2e5 + 10;
int n, m, q, par[N], sz[N], max_w[N], ans[N];
vector<tuple<int, int, int>> edges;
tuple<int, int, int, int> quer[N];
void pre_dsu()
{
    for (int i = 1; i <= n; i++)
    {
        par[i] = i;
        sz[i] = 1;
        max_w[i] = 0;
    }
}
int find(int u)
{
    return par[u] = (par[u] == u ? u : find(par[u]));
}
void Union(int u, int v, int w)
{
    u = find(u);
    v = find(v);
    max_w[u] = max(max(max_w[u], max_w[v]), w);
    if (u == v)
        return;
    if (sz[u] < sz[v])
        swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({w, u, v});
    }
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= q; i++)
    {
        int a, b, p;
        cin >> a >> b >> p;
        quer[i] = {p, a, b, i};
    }
    sort(quer + 1, quer + q + 1);
    pre_dsu();
    int j = -1;
    for (int i = 1; i <= q; i++)
    {
        int a, b, p, id;
        tie(p, a, b, id) = quer[i];
        while (j + 1 < m)
        {
            int u, v, w;
            tie(w, u, v) = edges[j + 1];
            if (w > p)
                break;
            Union(u, v, w);
            j++;
        }
        if (find(a) == find(b) and max_w[find(a)] <= p)
        {
            ans[id] = 1;
        }
    }
    for (int i = 1; i <= q; i++)
        if (ans[i])
            cout << "TAIP\n";
        else
            cout << "NE\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...