Submission #1182810

#TimeUsernameProblemLanguageResultExecution timeMemory
1182810nagornzDrivers (BOI24_drivers)C++20
100 / 100
114 ms18856 KiB
#include <bits/stdc++.h> #define int long long #define double long double #define pii pair <int,int> #define tiii tuple <int, int, int> #define tiiii tuple <int, int, int, int> #define f first #define s second #define all(x) x.begin(), x.end() #define ub(a, b) upper_bound(a.begin(), a.end(), b) - a.begin() #define lb(a, b) lower_bound(a.begin(), a.end(), b) - a.begin() #define ve vector #define graph(a, n) vector <int> a[n]; #define wgraph(a, n) vector <pii> a[n]; #define emb emplace_back #define em emplace #define ins insert #define er erase #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) using namespace std; template <typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>; const int mod = 1e9 + 7; const int inf = 1e18; const int N = 2e5 + 5; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int n, m, q; vector <int> par(N); vector <tiii> edge; vector <tiiii> query; bool ans[N]; int dsu(int a, vector <int> &par) { return par[a] = (par[a] == a ? a : dsu(par[a], par)); } int32_t main(){ iShowSpeed; cin >> n >> m >> q; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; edge.emb(w, u, v); } sort(all(edge)); // for (auto [w, u, v] : edge) cout << u << " -> " << v << ": " << w << "\n"; for (int i = 0; i < q; i++) { int a, b, t; cin >> a >> b >> t; query.emb(t, a, b, i); } sort(all(query)); iota(all(par), 0ll); int curr = 0; for (auto [t, a, b, idx] : query) { while (curr < m && get <0> (edge[curr]) <= t) { auto [w, u, v] = edge[curr]; int x = dsu(u, par), y = dsu(v, par); if (x != y) { par[x] = y; } curr++; } // cout << idx << ": " << a << " -> " << b << ": " << t << ": " << curr << "\n"; if (dsu(a, par) == dsu(b, par)) ans[idx] = true; } for (int i = 0; i < q; i++) { cout << (ans[i] ? "TAIP\n" : "NE\n"); } }
#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...