#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bit>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <time.h>
#include <random>
#include <inttypes.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3,Ofast")
#define EPS 1e-9
#define PI acos(-1)
#define MAXN 200'005
#define MOD 1'000'000'007
#define INF 1'000'000'000'000
#define ll int64_t
#define int int32_t
#define short int16_t
#define si(n) if(scanf("%d", &n))
#define sl(n) scanf("%ld", &n);
#define sc(n) scanf("%c", &n);
#define sf(n) scanf("%f", &n);
#define slf(n) scanf("%lf", &n);
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define dbg(x) std::cerr << #x << ": " << x << std::endl;
typedef std::set<int> si;
typedef std::set<ll> sll;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
typedef std::vector<std::vector<int>> dvi;
typedef std::vector<std::vector<ll>> dvll;
typedef std::unordered_map<int , int> mi;
typedef std::unordered_map<ll , ll> mll;
ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b) * b;}
int N, M, Q;
bool res[MAXN];
int *par, *size;
std::vector<std::tuple<int, int, int>> edges;
std::vector<std::tuple<int, int, int, int>> queries;
//Union Psajimo
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bit>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <time.h>
#include <random>
#include <inttypes.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3,Ofast")
#define EPS 1e-9
#define PI acos(-1)
#define MAXN 200'005
#define MOD 1'000'000'007
#define INF 1'000'000'000'000
#define ll int64_t
#define int int32_t
#define short int16_t
#define si(n) if(scanf("%d", &n))
#define sl(n) scanf("%ld", &n);
#define sc(n) scanf("%c", &n);
#define sf(n) scanf("%f", &n);
#define slf(n) scanf("%lf", &n);
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define dbg(x) std::cerr << #x << ": " << x << std::endl;
typedef std::set<int> si;
typedef std::set<ll> sll;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
typedef std::vector<std::vector<int>> dvi;
typedef std::vector<std::vector<ll>> dvll;
typedef std::unordered_map<int , int> mi;
typedef std::unordered_map<ll , ll> mll;
ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b) * b;}
int N, M, Q;
bool res[MAXN];
int *par, *size;
std::vector<std::tuple<int, int, int>> edges;
std::vector<std::tuple<int, int, int, int>> queries;
//Union Psajimo
void DSU() {
for(int i = 1; i <= N; ++i) {
par[i] = i;
size[i] = 1;
}
}
int find(int a) {
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if(size[a] < size[b]) std::swap(a, b);
par[b] = a;
size[a] += size[b];
}
bool same(int a, int b) {
return find(a) == find(b);
}
signed main()
{
// freopen("file.out", "w", stdout);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin>>N>>M>>Q;
par = new int[N+1];
size = new int[N+1];
DSU();
for(int i = 0; i < M; ++i) {
int u, v, w;
std::cin>>u>>v>>w;
edges.pb({w, u, v});
}
for(int i = 0; i < Q; ++i) {
int a, b, p;
std::cin>>a>>b>>p;
queries.pb({p, a, b, i});
}
std::sort(all(edges));
std::sort(all(queries));
// for(auto [w, u, v] : edges) {
// std::cout<<u<<" "<<v<<" "<<w<<"\n";
// }
// std::cout<<"\n";
// for(auto [p, a, b] : queries) {
// std::cout<<a<<" "<<b<<" "<<p<<"\n";
// }
for(int i = 0; i < Q; ++i) {
int a, b, p, id, indx = 0, u, v, w = 0;
std::tie(p, a, b, id) = queries[i];
std::tie(w, u, v) = edges[0];
while(w <= p && indx < M) {
std::tie(w, u, v) = edges[indx++];
if(!same(u, v))
unite(u, v);
}
res[id] = same(a, b);
}
for(int i = 0; i < Q; ++i) {
if(res[i]) std::cout<<"TAIP"<<std::endl;
else std::cout<<"NE"<<std::endl;
}
delete[] par;
delete[] size;
return 0;
}
void DSU() {
for(int i = 1; i <= N; ++i) {
par[i] = i;
size[i] = 1;
}
}
int find(int a) {
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if(size[a] < size[b]) std::swap(a, b);
par[b] = a;
size[a] += size[b];
}
bool same(int a, int b) {
return find(a) == find(b);
}
signed main()
{
// freopen("file.out", "w", stdout);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin>>N>>M>>Q;
par = new int[N+1];
size = new int[N+1];
DSU();
for(int i = 0; i < M; ++i) {
int u, v, w;
std::cin>>u>>v>>w;
edges.pb({w, u, v});
}
for(int i = 0; i < Q; ++i) {
int a, b, p;
std::cin>>a>>b>>p;
queries.pb({p, a, b, i});
}
std::sort(all(edges));
std::sort(all(queries));
// for(auto [w, u, v] : edges) {
// std::cout<<u<<" "<<v<<" "<<w<<"\n";
// }
// std::cout<<"\n";
// for(auto [p, a, b] : queries) {
// std::cout<<a<<" "<<b<<" "<<p<<"\n";
// }
for(int i = 0; i < Q; ++i) {
int a, b, p, id, indx = 0, u, v, w = 0;
std::tie(p, a, b, id) = queries[i];
std::tie(w, u, v) = edges[0];
while(w <= p && indx < M) {
std::tie(w, u, v) = edges[indx++];
// if(!same(u, v))
unite(u, v);
}
res[id] = same(a, b);
}
for(int i = 0; i < Q; ++i) {
if(res[i]) std::cout<<"TAIP"<<std::endl;
else std::cout<<"NE"<<std::endl;
}
delete[] par;
delete[] size;
return 0;
}
Compilation message
Main.cpp: In function 'int64_t lcm(int64_t, int64_t)':
Main.cpp:131:44: error: use of multiversioned function without a default
131 | ll lcm(ll a, ll b) {return a/gcd(a, b) * b;}
| ^
Main.cpp: At global scope:
Main.cpp:133:5: error: redefinition of 'int32_t N'
133 | int N, M, Q;
| ^
Main.cpp:64:5: note: 'int32_t N' previously declared here
64 | int N, M, Q;
| ^
Main.cpp:133:8: error: redefinition of 'int32_t M'
133 | int N, M, Q;
| ^
Main.cpp:64:8: note: 'int32_t M' previously declared here
64 | int N, M, Q;
| ^
Main.cpp:133:11: error: redefinition of 'int32_t Q'
133 | int N, M, Q;
| ^
Main.cpp:64:11: note: 'int32_t Q' previously declared here
64 | int N, M, Q;
| ^
Main.cpp:134:6: error: redefinition of 'bool res [200005]'
134 | bool res[MAXN];
| ^~~
Main.cpp:65:6: note: 'bool res [200005]' previously declared here
65 | bool res[MAXN];
| ^~~
Main.cpp:135:6: error: redefinition of 'int32_t* par'
135 | int *par, *size;
| ^~~
Main.cpp:66:6: note: 'int32_t* par' previously declared here
66 | int *par, *size;
| ^~~
Main.cpp:135:12: error: redefinition of 'int32_t* size'
135 | int *par, *size;
| ^~~~
Main.cpp:66:12: note: 'int32_t* size' previously declared here
66 | int *par, *size;
| ^~~~
Main.cpp:136:40: error: redefinition of 'std::vector<std::tuple<int, int, int> > edges'
136 | std::vector<std::tuple<int, int, int>> edges;
| ^~~~~
Main.cpp:67:40: note: 'std::vector<std::tuple<int, int, int> > edges' previously declared here
67 | std::vector<std::tuple<int, int, int>> edges;
| ^~~~~
Main.cpp:137:45: error: redefinition of 'std::vector<std::tuple<int, int, int, int> > queries'
137 | std::vector<std::tuple<int, int, int, int>> queries;
| ^~~~~~~
Main.cpp:68:45: note: 'std::vector<std::tuple<int, int, int, int> > queries' previously declared here
68 | std::vector<std::tuple<int, int, int, int>> queries;
| ^~~~~~~
Main.cpp:223:6: error: redefinition of 'void DSU()'
223 | void DSU() {
| ^~~
Main.cpp:140:6: note: 'void DSU()' previously defined here
140 | void DSU() {
| ^~~
Main.cpp:230:5: error: redefinition of 'int32_t find(int32_t)'
230 | int find(int a) {
| ^~~~
Main.cpp:147:5: note: 'int32_t find(int32_t)' previously defined here
147 | int find(int a) {
| ^~~~
Main.cpp:235:6: error: redefinition of 'void unite(int32_t, int32_t)'
235 | void unite(int a, int b) {
| ^~~~~
Main.cpp:152:6: note: 'void unite(int32_t, int32_t)' previously defined here
152 | void unite(int a, int b) {
| ^~~~~
Main.cpp:244:6: error: redefinition of 'bool same(int32_t, int32_t)'
244 | bool same(int a, int b) {
| ^~~~
Main.cpp:161:6: note: 'bool same(int32_t, int32_t)' previously defined here
161 | bool same(int a, int b) {
| ^~~~
Main.cpp:248:8: error: redefinition of 'int main()'
248 | signed main()
| ^~~~
Main.cpp:165:8: note: 'int main()' previously defined here
165 | signed main()
| ^~~~
