#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,fma")
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define INF32 (0x3f3f3f3f)
#define INF64 (0x3f3f3f3f3f3f3f3fLL)
#define INF (INF32)
#define PI (3.14159265358979323846)
#define MOD (10e9+7)
#define typeof(x) remove_reference<decltype(x)>::type
#define _picktype(a,b) common_type<typeof(a),typeof(b)>::type
#define rep(i,a,b) for(_picktype((a),(b)) i=(a); i<(b); i++)
#define repr(i,a,b) for(_picktype((a),(b)) i=(a); i>=(b); i--)
#define fori(a,b) rep(i,(a),(b))
#define forj(a,b) rep(j,(a),(b))
#define fork(a,b) rep(k,(a),(b))
#define rfori(a,b) repr(i,(a),(b))
#define rforj(a,b) repr(j,(a),(b))
#define rfork(a,b) repr(k,(a),(b))
#define forit(a,b) for(auto it=(a); it!=(b); it++)
#define rforit(a,b) for(auto it=(a); it!=(b); it--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mset(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
void impossible() {cout << -1 << endl; exit(0);}
#if defined(_WIN64) || defined(_WIN32)
inline int getchar_unlocked() { return _getchar_nolock(); }
#endif
int getint() {
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar_unlocked();
}
return x;
}
ll getll() {
ll x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar_unlocked();
}
return x;
}
struct CustomHash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
size_t operator()(pair<uint64_t,uint64_t> x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
}
};
struct DSU {
vector<int> par;
DSU(int n) { par.clear(); par.resize(n, -1); }
int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
int root(int x) { return find(x); }
int parent(int x) { return find(x); }
bool connected(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (par[y] < par[x]) swap(x,y);
par[x] += par[y];
par[y] = x;
}
};
void solve() {
int V = getint(), E = getint(), Q = getint();
DSU d = DSU(V);
DSU d2 = DSU(V);
vector<int> res(V, -1);
vector<pair<int, pii>> edges(E);
fori(0,E) {
int a = getint(), b = getint(), q = getint();
a--; b--;
edges[i] = mp(q, mp(a,b));
}
sort(all(edges), greater<pair<int, pii>>());
fori(0,E) {
int q = edges[i].fi, a = edges[i].se.fi, b = edges[i].se.se;
if (d.connected(a, b)) continue;
if (!d.connected(0, a) && !d.connected(0, b)) {
d.merge(a,b);
d2.merge(a,b);
} else if (d.connected(0, a) && !d.connected(0, b)) {
res[d2.find(b)] = q;
d.merge(a,b);
} else {
res[d2.find(a)] = q;
d.merge(a,b);
}
}
fori(0,Q) {
int x = getint(); x--;
cout << res[d2.find(x)] << endl;
}
}
int main()
{
// ios::sync_with_stdio(0); cin.tie(0); cout.precision(10); cout<<fixed;
int t = 1;
// cin>>t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
635 ms |
41520 KB |
Output is correct |
| 2 |
Correct |
1142 ms |
167860 KB |
Output is correct |
