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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (300000 + 1)
#define MAXM (500000 + 5)
#define MAXT (100000 + 1)
#define MAXL (20 + 1)
#define LL long long
#define pii pair<int, int>
using namespace std;
struct node {
int le, ri, ls, rs, zh;
} b[MAXN * 9];
struct edg {
int from, to, cost, next;
} te[MAXM], tb[MAXN << 1];
int n, m, a[MAXN], cnta, fat[MAXN], fak[MAXN], d[MAXN][MAXL], tn, cntb, g[MAXN], di[MAXN], lgn, root[MAXN], cntn, h[MAXT], sorh[MAXT];
pii son[MAXN];
bool cmp(edg x, edg y) { return x.cost < y.cost; }
int find(int* fa, int x) { return (fa[x] == x) ? x : (fa[x] = find(fa, fa[x])); }
void uni(int* fa, int x, int y) { fa[find(fa, x)] = find(fa, y); }
int lg(int x) {
int re = 0;
while ((1 << re) < x) ++re;
return re;
}
void adn(int from, int to) {
tb[++cntb].next = g[from];
tb[cntb].from = from, tb[cntb].to = to;
g[from] = cntb;
}
void kruskal() {
sort(te + 1, te + m + 1, cmp);
for (int i = 1; i < MAXN; i++) fat[i] = fak[i] = i;
int cnte = 0;
tn = n;
for (int i = 1; i <= m; i++)
if (find(fat, te[i].from) != find(fat, te[i].to)) {
if (!di[te[i].from]) di[te[i].from] = te[i].cost;
if (!di[te[i].to]) di[te[i].to] = te[i].cost;
di[++tn] = te[i].cost;
adn(tn, find(fak, te[i].from)), adn(find(fak, te[i].from), tn);
adn(tn, find(fak, te[i].to)), adn(find(fak, te[i].to), tn);
uni(fat, te[i].from, te[i].to);
uni(fak, te[i].from, tn), uni(fak, te[i].to, tn);
++cnte;
if (cnte == n - 1) break;
}
}
void dfs(int dq) {
a[son[dq].first = ++cnta] = dq;
for (int i = 1; i <= lgn; i++) d[dq][i] = d[d[dq][i - 1]][i - 1];
for (int i = g[dq]; i; i = tb[i].next)
if (tb[i].to != d[dq][0])
d[tb[i].to][0] = dq, dfs(tb[i].to);
son[dq].second = cnta;
}
int cxroot(int x, int cap) {
for (int i = lgn; i >= 0; i--)
if (di[d[x][i]] <= cap)
x = d[x][i];
return x;
}
void ins(int pre, int& dq, int le, int ri, int wz, int zh) {
dq = ++cntn;
b[dq].le = le, b[dq].ri = ri, b[dq].zh = b[pre].zh + zh;
if (le == ri) return ;
int mi = (le + ri) >> 1;
if (wz <= mi) b[dq].rs = b[pre].rs, ins(b[pre].ls, b[dq].ls, le, mi, wz, zh);
else b[dq].ls = b[pre].ls, ins(b[pre].rs, b[dq].rs, mi + 1, ri, wz, zh);
}
int cx(int pre, int dq, int k) {
if (b[dq].zh - b[pre].zh < k) return -1;
if (b[dq].le == b[dq].ri) return b[dq].le;
if (b[b[dq].rs].zh - b[b[pre].rs].zh >= k) return cx(b[pre].rs, b[dq].rs, k);
else return cx(b[pre].ls, b[dq].ls, k - b[b[dq].rs].zh + b[b[pre].rs].zh);
}
inline int read() {
int re = 0;
char x = 0;
while (x < '0' || x > '9') x = getchar();
while (x >= '0' && x <= '9') re = (re << 1) + (re << 3) + x - '0', x = getchar();
return re;
}
int main() {
int q;
n = read(), m = read(), q = read();
lgn = lg(n);
for (int i = 1; i <= n; i++) h[i] = read(), sorh[++sorh[0]] = h[i];
sort(sorh + 1, sorh + sorh[0] + 1);
sorh[0] = unique(sorh + 1, sorh + sorh[0] + 1) - sorh - 1;
for (int i = 1; i <= n; i++) h[i] = lower_bound(sorh + 1, sorh + sorh[0] + 1, h[i]) - sorh;
for (int i = 1; i <= m; i++) te[i].from = read(), te[i].to = read(), te[i].cost = read();
kruskal();
d[tn][0] = tn;
dfs(tn);
for (int i = 1; i <= cnta; i++) ins(root[i - 1], root[i], 1, sorh[0], (a[i] <= n) ? h[a[i]] : 1, a[i] <= n);
for (int i = 1, lastans = 0, srf, src, srk; i <= q; i++) {
srf = read(), src = read(), srk = read();
if (lastans == -1) lastans = 0;
srf ^= lastans, src ^= lastans, srk ^= lastans;
int mindn = cxroot(srf, src);
lastans = cx(root[son[mindn].first - 1], root[son[mindn].second], srk);
if (~lastans) lastans = sorh[lastans];
printf("%d\n", lastans);
}
return 0;
}
|