結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 LayCurse
|
| 提出日時 | 2017-06-28 23:16:09 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 258 ms / 4,500 ms |
| コード長 | 22,661 bytes |
| コンパイル時間 | 2,043 ms |
| コンパイル使用メモリ | 163,944 KB |
| 実行使用メモリ | 36,580 KB |
| 最終ジャッジ日時 | 2023-08-22 11:05:37 |
| 合計ジャッジ時間 | 5,995 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
9,436 KB |
| testcase_01 | AC | 5 ms
9,496 KB |
| testcase_02 | AC | 4 ms
9,452 KB |
| testcase_03 | AC | 4 ms
9,472 KB |
| testcase_04 | AC | 5 ms
9,552 KB |
| testcase_05 | AC | 5 ms
9,508 KB |
| testcase_06 | AC | 5 ms
9,568 KB |
| testcase_07 | AC | 5 ms
9,584 KB |
| testcase_08 | AC | 79 ms
20,892 KB |
| testcase_09 | AC | 82 ms
21,704 KB |
| testcase_10 | AC | 121 ms
22,772 KB |
| testcase_11 | AC | 123 ms
22,572 KB |
| testcase_12 | AC | 109 ms
23,032 KB |
| testcase_13 | AC | 183 ms
36,580 KB |
| testcase_14 | AC | 66 ms
27,616 KB |
| testcase_15 | AC | 220 ms
23,760 KB |
| testcase_16 | AC | 225 ms
23,756 KB |
| testcase_17 | AC | 254 ms
33,388 KB |
| testcase_18 | AC | 258 ms
33,896 KB |
| testcase_19 | AC | 230 ms
30,456 KB |
ソースコード
#include<bits/stdc++.h>
using namespace std;
void *wmem;
void rd(int &x){
int k, m=0;
x=0;
for(;;){
k = getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
void wt_L(int x){
char f[10];
int m=0, s=0;
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
putchar_unlocked('-');
}
while(s--){
putchar_unlocked(f[s]+'0');
}
}
template<class S, class T> inline S min_L(S a,T b){
return a<=b?a:b;
}
template<class S, class T> inline S max_L(S a,T b){
return a>=b?a:b;
}
template<class S, class T> inline S chmin(S &a, T b){
if(a>b){
a=b;
}
return a;
}
template<class T> struct segtree{
T *addval, *fixval, *mn, *sum;
char *fixed;
int N, logN, *mnind;
void malloc(int maxN, int once = 0){
int i;
for(i=1;i<maxN;i*=2){
;
}
sum = (T*)std::malloc(sizeof(T)*2*i);
mn = (T*)std::malloc(sizeof(T)*2*i);
mnind = (int*)std::malloc(sizeof(T)*2*i);
fixval = (T*)std::malloc(sizeof(T)*i);
addval = (T*)std::malloc(sizeof(T)*i);
fixed = (char*)std::malloc(sizeof(char)*i);
if(once){
setN(maxN);
}
}
void walloc(int maxN, int once = 0, void **mem = &wmem){
int i;
for(i=1;i<maxN;i*=2){
;
}
sum = (T*)(*mem);
mn = sum + 2*i;
mnind = (int*)(mn + 2*i);
fixval = (T*)(mnind + 2*i);
addval = fixval + i;
fixed = (char*)(addval + i);
*mem = fixed + i;
if(once){
setN(maxN);
}
}
void free(void){
std::free(sum);
std::free(mn);
std::free(mnind);
std::free(fixval);
std::free(addval);
std::free(fixed);
}
T& operator[](int i){
return sum[N+i];
}
void setN(int n, int zerofill = 1, int dobuild = 1){
int i;
for(i=1,logN=0;i<n;i*=2,logN++){
;
}
N = i;
if(zerofill){
for(i=0;i<N;i++){
sum[N+i] = 0;
}
}
if(dobuild){
build();
}
}
void build(void){
int i;
for(i=0;i<N;i++){
mn[N+i] = sum[N+i];
mnind[N+i] = i;
}
for(i=N-1;i;i--){
sum[i] = sum[2*i] + sum[2*i+1];
if(mn[2*i] <= mn[2*i+1]){
mn[i] = mn[2*i];
mnind[i] = mnind[2*i];
}
else{
mn[i] = mn[2*i+1];
mnind[i] = mnind[2*i+1];
}
}
for(i=1;i<N;i++){
fixed[i] = 0;
}
for(i=1;i<N;i++){
addval[i] = 0;
}
}
inline void push_one(int a, int sz, int st){
if(fixed[a]){
if(sz > 1){
fixed[a*2] = fixed[a*2+1] = 1;
fixval[a*2] = fixval[a*2+1] = fixval[a];
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
else{
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
fixed[a] = 0;
addval[a] = 0;
return;
}
if(addval[a] != 0){
if(sz > 1){
if(fixed[a*2]){
fixval[a*2] += addval[a];
}
else{
addval[a*2] += addval[a];
}
if(fixed[a*2+1]){
fixval[a*2+1] += addval[a];
}
else{
addval[a*2+1] += addval[a];
}
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
else{
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
addval[a] = 0;
return;
}
}
inline void push(int a){
int aa=a - N, i, nd, st, sz;
for(i=logN;i;i--){
nd = a>>i;
sz = 1<<(i-1);
st = 2 * sz * (aa>>i);
push_one(nd, sz, st);
}
}
inline void build(int a){
int st=a - N, sz=1;
while(a > 1){
if(a%2){
st += sz;
}
a /= 2;
sz *= 2;
if(fixed[a]){
sum[a] = sz * fixval[a];
mn[a] = fixval[a];
}
else{
sum[a] = sum[a*2] + sum[a*2+1];
if(mn[a*2] <= mn[a*2+1]){
mn[a] = mn[a*2];
mnind[a] = mnind[a*2];
}
else{
mn[a] = mn[a*2+1];
mnind[a] = mnind[a*2+1];
}
if(addval[a] != 0){
mn[a] += addval[a];
sum[a] += sz * addval[a];
}
}
}
}
inline void change(int a, int b, T val){
int aa, bb, st_a=a, st_b=b, sz=1;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] = mn[a] = val;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
sum[b] = mn[b] = val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
fixed[a]=1;
fixval[a]=val;
sum[a] = sz * val;
mn[a] = val;
mnind[a] = st_a;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
fixed[b]=1;
fixval[b]=val;
sum[b] = sz * val;
mn[b] = val;
mnind[b] = st_b;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline void add(int a, int b, T val){
int aa, bb, sz=1;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] += val;
mn[a] += val;
a++;
}
if(b%2){
b--;
sum[b] += val;
mn[b] += val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
if(fixed[a]){
fixval[a] += val;
}
else{
addval[a] += val;
}
sum[a] += sz * val;
mn[a] += val;
a++;
}
if(b%2){
b--;
if(fixed[b]){
fixval[b] += val;
}
else{
addval[b] += val;
}
sum[b] += sz * val;
mn[b] += val;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline pair<T,int> getMin(int a, int b){
int sz=1;
pair<T,int> res;
a += N;
b += N;
push(a);
push(b-1);
res.first = numeric_limits<T>::max();
res.second = -1;
while(a < b){
if(a%2){
chmin(res, make_pair(mn[a], mnind[a]));
a++;
}
if(b%2){
b--;
chmin(res, make_pair(mn[b], mnind[b]));
}
a /= 2;
b /= 2;
}
return res;
}
inline T getMinVal(int a, int b){
return getMin(a,b).first;
}
inline int getMinInd(int a, int b){
return getMin(a,b).second;
}
inline T getSum(int a, int b){
T res;
int sz=1;
a += N;
b += N;
push(a);
push(b-1);
res = 0;
while(a < b){
if(a%2){
res += sum[a++];
}
if(b%2){
res += sum[--b];
}
a /= 2;
b /= 2;
}
return res;
}
}
;
struct graph{
int N, **edge, *es;
void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
int i;
N = N__;
es = (int*)(*mem);
edge = (int**)(es+N);
edge[0] = (int*)(edge+N);
for(i=0;i<N;i++){
es[i] = 0;
}
for(i=0;i<M;i++){
es[A[i]]++;
es[B[i]]++;
}
for(i=1;i<N;i++){
edge[i] = edge[i-1] + es[i-1];
}
(*mem) = edge[N-1] + es[N-1];
for(i=0;i<N;i++){
es[i] = 0;
}
for(i=0;i<M;i++){
edge[A[i]][es[A[i]]++] = B[i];
edge[B[i]][es[B[i]]++] = A[i];
}
}
void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
int i;
N = N__;
es = (int*)(*mem);
edge = (int**)(es+N);
edge[0] = (int*)(edge+N);
for(i=0;i<N;i++){
es[i] = 0;
}
for(i=0;i<M;i++){
es[A[i]]++;
}
for(i=1;i<N;i++){
edge[i] = edge[i-1] + es[i-1];
}
(*mem) = edge[N-1] + es[N-1];
for(i=0;i<N;i++){
es[i] = 0;
}
for(i=0;i<M;i++){
edge[A[i]][es[A[i]]++] = B[i];
}
}
graph reverse(void **mem = &wmem){
graph g;
int i, j, k;
g.N = N;
g.es = (int*)(*mem);
g.edge = (int**)(g.es + N);
g.edge[0] = (int*)(g.edge + N);
for(i=0;i<N;i++){
g.es[i] = 0;
}
for(i=0;i<N;i++){
for(j=0;j<es[i];j++){
g.es[edge[i][j]]++;
}
}
for(i=1;i<N;i++){
g.edge[i] = g.edge[i-1] + g.es[i-1];
}
*mem = g.edge[N-1] + g.es[N-1];
for(i=0;i<N;i++){
g.es[i] = 0;
}
for(i=0;i<N;i++){
for(j=0;j<es[i];j++){
k = edge[i][j];
g.edge[k][g.es[k]++] = i;
}
}
return g;
}
graph reduce(int tn, int ind[], int self_e = 0, int dep_e = 0, void **mem = &wmem){
graph g;
int M=0, i, j, k, x, y;
pair<int,int> *A;
for(i=0;i<N;i++){
M += es[i];
}
A = (pair<int,int>*)((int*)((int**)(*mem) + tn) + tn + M);
M = 0;
for(i=0;i<N;i++){
x = ind[i];
if(x < 0){
continue;
}
for(j=0;j<es[i];j++){
y = ind[edge[i][j]];
if(y < 0){
continue;
}
if(self_e==0 && x==y){
continue;
}
A[M++] = make_pair(x, y);
}
}
if(dep_e==0){
sort(A, A+M);
k = 0;
for(i=0;i<M;i++){
if(k && A[k-1]==A[i]){
continue;
}
A[k++] = A[i];
}
M = k;
}
g.N = tn;
g.es = (int*)(*mem);
g.edge = (int**)(g.es + tn);
g.edge[0] = (int*)(g.edge + tn);
for(i=0;i<tn;i++){
g.es[i] = 0;
}
for(i=0;i<M;i++){
g.es[A[i].first]++;
}
for(i=1;i<tn;i++){
g.edge[i] = g.edge[i-1] + g.es[i-1];
}
*mem = g.edge[tn-1] + g.es[tn-1];
for(i=0;i<tn;i++){
g.es[i] = 0;
}
for(i=0;i<M;i++){
j = A[i].first;
k = A[i].second;
g.edge[j][g.es[j]++] = k;
}
return g;
}
void getDist(int root, int res[], void *mem = wmem){
int i, j, k, *q, s, z;
q=(int*)mem;
for(i=0;i<N;i++){
res[i]=-1;
}
res[root]=0;
s=0;
z=1;
q[0]=root;
while(z){
i=q[s++];
z--;
for(j=0;j<es[i];j++){
k=edge[i][j];
if(res[k]>=0){
continue;
}
res[k]=res[i]+1;
q[s+z++]=k;
}
}
}
inline int sccDFS(int num[], int st, int mx){
int i, j;
num[st]=-2;
for(i=0;i<es[st];i++){
j=edge[st][i];
if(num[j]==-1){
mx=sccDFS(num,j,mx);
}
}
num[st]=mx;
return mx+1;
}
int scc(int res[], void *mem = wmem){
graph r;
int i, j, k, *nrv, *num, ret=0, *st, st_size;
r = reverse(&mem);
st = (int*)mem;
num = st+N;
nrv = num + N;
for(i=0;i<N;i++){
res[i] = num[i] = -1;
}
k = 0;
for(i=0;i<N;i++){
if(num[i]==-1){
k = sccDFS(num,i,k);
}
}
for(i=0;i<N;i++){
nrv[num[i]] = i;
}
for(k=N-1;k>=0;k--){
i=nrv[k];
if(res[i]>=0){
continue;
}
res[i]=ret;
st_size=0;
st[st_size++]=i;
while(st_size){
i=st[--st_size];
for(j=0;j<r.es[i];j++){
if(res[r.edge[i][j]]==-1){
res[r.edge[i][j]]=ret;
st[st_size++]=r.edge[i][j];
}
}
}
ret++;
}
return ret;
}
inline void bccDFS(int v, int u, int *res, int *rt, int &rts, int *S, int &Ss, int *inS, int *num, int &tm){
int i, k;
num[v] = ++tm;
S[Ss++] = v;
inS[v] = 1;
rt[rts++] = v;
for(i=0;i<es[v];i++){
int w=edge[v][i];
if(!num[w]){
bccDFS(w, v, res, rt, rts, S, Ss, inS, num, tm);
}
else if(u != w && inS[w]){
while(num[rt[rts-1]] > num[w]){
rts--;
}
}
}
if(v == rt[rts-1]){
k = S[Ss-1];
for(;;){
int w=S[--Ss];
inS[w] = 0;
res[w] = k;
if(v==w){
break;
}
}
rts--;
}
}
int bcc(int res[], void *mem=wmem){
int *S, Ss=0, i, *inS, k, *num, *rt, rts=0, tm=0;
pair<int,int> *arr;
num = (int*)mem;
rt = num + N;
S = rt + N;
inS = S + N;
memset(num, 0, sizeof(int)*N);
memset(inS, 0, sizeof(int)*N);
for(i=0;i<N;i++){
if(!num[i]){
bccDFS(i, N, res, rt, rts, S, Ss, inS, num, tm);
}
}
arr = (pair<int,int>*)mem;
for(i=0;i<N;i++){
arr[i].first = res[i];
arr[i].second = i;
}
sort(arr, arr+N);
k = 0;
for(i=0;i<N;i++){
if(i && arr[i].first != arr[i-1].first){
k++;
}
res[arr[i].second] = k;
}
return k+1;
}
}
;
struct HLD{
int N, **edge, *es, *group, *groupDepth, **groupNode, groupNum, *groupSize, *groupUpNode, *groupind;
void init(graph g, void **mem = &wmem){
init(g.N, g.es, g.edge, mem);
}
void init(int N__, int *es__, int **edge__, void **mem = &wmem){
char *vis;
int i, j, k, mx, *q, q_ed, q_st, *sz, x, y;
N = N__;
es = es__;
edge = edge__;
group = (int*)(*mem);
groupind = group + N;
*mem = groupind + N;
q = (int*)(*mem);
sz = q + N;
vis = (char*)(sz + N);
for(i=0;i<N;i++){
vis[i] = 0;
}
q_st = 0;
q_ed = 1;
q[0] = 0;
vis[0] = 1;
while(q_st < q_ed){
i = q[q_st++];
for(j=0;j<es[i];j++){
k = edge[i][j];
if(!vis[k]){
vis[k] = 1;
q[q_ed++] = k;
}
}
}
for(i=0;i<N;i++){
sz[i] = 0;
}
for(j=N-1;j>=0;j--){
i = q[j];
sz[i] = 1;
for(k=0;k<es[i];k++){
sz[i] += sz[edge[i][k]];
}
}
for(i=0;i<N;i++){
group[i] = -1;
}
groupNum = 0;
for(j=0;j<N;j++){
i = q[j];
if(group[i]>=0){
continue;
}
group[i] = groupNum++;
groupind[i] = 0;
for(;;){
mx = -1;
for(k=0;k<es[i];k++){
if(group[edge[i][k]] != -1){
continue;
}
if(mx==-1){
mx = k;
}
else if(sz[edge[i][k]] > sz[edge[i][mx]]){
mx = k;
}
}
if(mx==-1){
break;
}
group[edge[i][mx]] = group[i];
groupind[edge[i][mx]] = groupind[i]+1;
i = edge[i][mx];
}
}
groupSize = (int*)(*mem);
groupUpNode = groupSize + groupNum;
groupDepth = groupUpNode + groupNum;
for(i=0;i<groupNum;i++){
groupSize[i] = 0;
}
for(i=0;i<N;i++){
groupSize[group[i]]++;
}
groupNode = (int**)(groupDepth + groupNum);
groupNode[0] = (int*)(groupNode + groupNum);
for(i=1;i<groupNum;i++){
groupNode[i] = groupNode[i-1] + groupSize[i-1];
}
*mem = groupNode[groupNum-1] + groupSize[groupNum-1];
for(i=0;i<N;i++){
groupNode[group[i]][groupind[i]] = i;
}
for(i=0;i<groupNum;i++){
groupDepth[i] = -1;
}
groupUpNode[0] = -1;
groupDepth[0] = 0;
for(x=0;x<groupNum;x++){
for(y=0;y<groupSize[x];y++){
i = groupNode[x][y];
for(j=0;j<es[i];j++){
k = edge[i][j];
if(x != group[k] && groupDepth[group[k]]==-1){
groupUpNode[group[k]] = i;
groupDepth[group[k]] = groupDepth[x] + 1;
}
}
}
}
}
int lca(int x, int y){
int x1, x2, y1, y2;
x1 = group[x];
x2 = groupind[x];
y1 = group[y];
y2 = groupind[y];
while(groupDepth[x1] > groupDepth[y1]){
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
while(groupDepth[x1] < groupDepth[y1]){
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
while(x1 != y1){
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
if(x2 <= y2){
return x;
}
return y;
}
int depth(int x){
int res=0, x1, x2;
x1 = group[x];
x2 = groupind[x];
while(groupUpNode[x1] != -1){
res += x2 + 1;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
return res + x2;
}
int dist(int x, int y){
int res=0, x1, x2, y1, y2;
x1 = group[x];
x2 = groupind[x];
y1 = group[y];
y2 = groupind[y];
while(groupDepth[x1] > groupDepth[y1]){
res += x2 + 1;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
while(groupDepth[x1] < groupDepth[y1]){
res += y2 + 1;
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
while(x1 != y1){
res += x2 + y2 + 2;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
if(x2 <= y2){
return res + y2 - x2;
}
return res + x2 - y2;
}
int up(int x){
int x1=group[x], x2=groupind[x];
if(x2==0){
return groupUpNode[x1];
}
return groupNode[x1][x2-1];
}
int up(int x, int d){
int x1=group[x], x2=groupind[x];
while(d > x2){
if(groupUpNode[x1]==-1){
return -1;
}
d -= x2 + 1;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
return groupNode[x1][x2-d];
}
}
;
template<class T> struct HLD_segtree{
HLD *hld;
segtree<T> *seg;
void init(HLD *hld__, T initval[], void **mem = &wmem){
int i, j;
hld = hld__;
seg = (segtree<T>*)(*mem);
*mem = seg + hld->groupNum;
for(i=0;i<hld->groupNum;i++){
seg[i].walloc(hld->groupSize[i], 0, mem);
seg[i].setN(hld->groupSize[i], 0, 0);
if(initval!=NULL){
for(j=0;j<hld->groupSize[i];j++){
seg[i][j] = initval[ hld->groupNode[i][j] ];
}
}
else{
for(j=0;j<hld->groupSize[i];j++){
seg[i][j] = 0;
}
}
seg[i].build();
}
}
inline void change(int u, int v, T val){
int ug, ui, vg, vi;
ug = hld->group[u];
vg = hld->group[v];
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
seg[ug].change(0, hld->groupind[u]+1, val);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
seg[ug].change(min_L(ui, vi),max_L(ui, vi)+1, val);
}
inline void add(int u, int v, T val){
int ug, ui, vg, vi;
ug = hld->group[u];
vg = hld->group[v];
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
seg[ug].add(0, hld->groupind[u]+1, val);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
seg[ug].add(min_L(ui, vi),max_L(ui, vi)+1, val);
}
inline pair<T,int> getMin(int u, int v){
int ug, ui, vg, vi;
pair<T,int> res, tmp;
ug = hld->group[u];
vg = hld->group[v];
res.first = numeric_limits<T>::max();
res.second = -1;
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
tmp = seg[ug].getMin(0, hld->groupind[u]+1);
tmp.second = hld->groupNode[ug][tmp.second];
chmin(res, tmp);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
tmp = seg[ug].getMin(min_L(ui, vi),max_L(ui, vi)+1);
tmp.second = hld->groupNode[ug][tmp.second];
chmin(res, tmp);
return res;
}
inline T getMinVal(int u, int v){
return getMin(u,v).first;
}
inline int getMinInd(int u, int v){
return getMin(u,v).second;
}
inline T getSum(int u, int v){
T res;
int ug, ui, vg, vi;
ug = hld->group[u];
vg = hld->group[v];
res = 0;
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
res += seg[ug].getSum(0, hld->groupind[u]+1);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
res += seg[ug].getSum(min_L(ui, vi),max_L(ui, vi)+1);
return res;
}
}
;
char memarr[64000000];
int A[200000], B[200000], M, N, Q, X, Y, Z, cnv[100000], tn, val[100000];
priority_queue<int> q[100000];
int main(){
HLD hld;
HLD_segtree<int> t;
graph g, og;
int i, j, k;
wmem = memarr;
rd(N);
rd(M);
rd(Q);
{
int Lj4PdHRW;
for(Lj4PdHRW=0;Lj4PdHRW<M;Lj4PdHRW++){
rd(A[Lj4PdHRW]);
rd(B[Lj4PdHRW]);
}
}
{
int KL2GvlyY;
for(KL2GvlyY=0;KL2GvlyY<(M-1) + 1;KL2GvlyY++){
A[KL2GvlyY]--;
}
}
{
int Q5VJL1cS;
for(Q5VJL1cS=0;Q5VJL1cS<(M-1) + 1;Q5VJL1cS++){
B[Q5VJL1cS]--;
}
}
og.setEdge(N,M,A,B);
tn = og.bcc(cnv);
g = og.reduce(tn, cnv);
{
int e98WHCEY;
for(e98WHCEY=0;e98WHCEY<(tn-1) + 1;e98WHCEY++){
val[e98WHCEY] = 1;
}
}
hld.init(g);
t.init(&hld, val);
{
int cTE1_r3A;
for(cTE1_r3A=0;cTE1_r3A<(tn-1) + 1;cTE1_r3A++){
val[cTE1_r3A] = -1;
}
}
while(Q--){
rd(X);
rd(Y);
rd(Z);
if(X==1){
Y = cnv[Y-1];
q[Y].push(Z);
if(val[Y] < Z){
val[Y] = Z;
t.change(Y,Y,-Z);
}
}
else{
Y = cnv[Y-1];
Z = cnv[Z-1];
k = t.getMinInd(Y, Z);
wt_L(val[k]);
putchar_unlocked('\n');
if(val[k]==-1){
continue;
}
q[k].pop();
if(q[k].size()){
Z = q[k].top();
}
else{
Z = -1;
}
val[k] = Z;
t.change(k,k,-Z);
}
}
return 0;
}
// cLay varsion 20170628-1
// --- original code ---
// int N, M, Q;
// int A[200000], B[200000];
// int X, Y, Z;
//
// int tn;
// int cnv[100000];
// int val[100000];
// priority_queue<int> q[100000];
// {
// int i, j, k;
// graph og, g;
// HLD hld;
// HLD_segtree<int> t;
//
// rd(N,M,Q,(A,B)(M));
// A[0..M-1]--;
// B[0..M-1]--;
// og.setEdge(N,M,A,B);
// tn = og.bcc(cnv);
// g = og.reduce(tn, cnv);
//
// val[0..tn-1] = 1;
// hld.init(g);
// t.init(&hld, val);
// val[0..tn-1] = -1;
//
// while(Q--){
// rd(X,Y,Z);
// if(X==1){
// Y = cnv[Y-1];
// q[Y].push(Z);
// if(val[Y] < Z){
// val[Y] = Z;
// t.change(Y,Y,-Z);
// }
// } else {
// Y = cnv[Y-1];
// Z = cnv[Z-1];
// k = t.getMinInd(Y, Z);
// wt(val[k]);
// if(val[k]==-1) continue;
// q[k].pop();
// if(q[k].size()) Z = q[k].top(); else Z = -1;
// val[k] = Z;
// t.change(k,k,-Z);
// }
// }
// }