1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include <bits/stdc++.h> #define MAX_N 100000 #define MAX_M 500000 #define mid ((s+t)>>1) using namespace std; template <class T> inline void read(T &x) { x = 0; int c = getchar(), f = 1; for (; !isdigit(c); c = getchar()) if (c == 45) f = -1; for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0'); } int N, M, Q, sz, h[MAX_N+5]; int fa[MAX_N+5], rt[MAX_N+5], ans[MAX_M+5]; int val[MAX_N+5], rev[MAX_N+5], tot; map <int, int> mp; struct edge {int u, v, c;} E[MAX_M+5]; struct node {int ls, rs, s;} tr[MAX_N*50]; struct quest {int id, u, c, k;} q[MAX_M+5]; bool cmpe(const edge &a, const edge &b) {return a.c < b.c;} bool cmpq(const quest &a, const quest &b) {return a.c < b.c;} int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);} void modify(int &v, int s, int t, int p) { if (!v) v = ++sz; if (s == t) {tr[v].s++; return;} if (p <= mid) modify(tr[v].ls, s, mid, p); if (p >= mid+1) modify(tr[v].rs, mid+1, t, p); tr[v].s = tr[tr[v].ls].s+tr[tr[v].rs].s; } int query(int v, int s, int t, int k) { if (s == t) return s; int rsz = tr[tr[v].rs].s; if (rsz < k) return query(tr[v].ls, s, mid, k-rsz); return query(tr[v].rs, mid+1, t, k); } int merge(int x, int y) { if (!x) return y; if (!y) return x; tr[x].s = tr[x].s+tr[y].s; tr[x].ls = merge(tr[x].ls, tr[y].ls); tr[x].rs = merge(tr[x].rs, tr[y].rs); return x; } int main() { read(N), read(M), read(Q); for (int i = 1; i <= N; i++) fa[i] = i; for (int i = 1; i <= N; i++) read(h[i]); for (int i = 1; i <= N; i++) val[i] = h[i]; sort(val+1, val+N+1); for (int i = 1; i <= N; i++) if (i == 1 || (val[i]^val[i-1])) mp[val[i]] = ++tot, rev[tot] = val[i]; for (int i = 1; i <= N; i++) h[i] = mp[h[i]]; for (int i = 1; i <= N; i++) modify(rt[i], 1, N, h[i]); for (int i = 1, u, v, c; i <= M; i++) read(u), read(v), read(c), E[i] = (edge){u, v, c}; for (int i = 1, u, c, k; i <= Q; i++) read(u), read(c), read(k), q[i] = (quest){i, u, c, k}; sort(E+1, E+M+1, cmpe), sort(q+1, q+Q+1, cmpq); for (int i = 1, j = 1, lft = N-1; i <= Q; i++) { for (int u, v; lft && j <= M && E[j].c <= q[i].c; j++) if ((u = getf(E[j].u)) ^ (v = getf(E[j].v))) fa[v] = u, rt[u] = merge(rt[u], rt[v]), lft--; int v = rt[getf(q[i].u)]; if (tr[v].s < q[i].k) ans[q[i].id] = -1; else ans[q[i].id] = rev[query(v, 1, N, q[i].k)]; } for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]); return 0; }
|