結果

問題 No.901 K-ary εxtrεεmε
ユーザー LayCurseLayCurse
提出日時 2019-10-04 22:13:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 93 ms / 3,000 ms
コード長 14,886 bytes
コンパイル時間 3,517 ms
コンパイル使用メモリ 231,776 KB
最終ジャッジ日時 2025-01-07 20:35:36
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
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 T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){
sort(a, a+N);
}
template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
int i;
pair<T1, T2> *arr;
walloc1d(&arr, N, &mem);
for(i=(0);i<(N);i++){
arr[i].first = a[i];
arr[i].second = b[i];
}
sort(arr, arr+N);
for(i=(0);i<(N);i++){
a[i] = arr[i].first;
b[i] = arr[i].second;
}
}
inline void rd(int &x){
int k;
int 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;
}
}
inline int rd_int(void){
int x;
rd(x);
return x;
}
inline void wt_L(char a){
putchar_unlocked(a);
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
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 T> struct LHeap{
int *hp;
int *place;
int size;
T *val;
void malloc(int N){
hp = (int*)std::malloc(N*sizeof(int));
place=(int*)std::malloc(N*sizeof(int));
val=(T*)std::malloc(N*sizeof(T));
}
void walloc(int N, void **mem=&wmem){
walloc1d(&hp, N, mem);
walloc1d(&place, N, mem);
walloc1d(&val, N, mem);
}
void free(){
std::free(hp);
std::free(place);
std::free(val);
}
void init(int N){
int i;
size=0;
for(i=(0);i<(N);i++){
place[i]=-1;
}
}
void up(int n){
int m;
while(n){
m=(n-1)/2;
if(val[hp[m]]<=val[hp[n]]){
break;
}
swap(hp[m],hp[n]);
swap(place[hp[m]],place[hp[n]]);
n=m;
}
}
void down(int n){
int m;
for(;;){
m=2*n+1;
if(m>=size){
break;
}
if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
m++;
}
if(val[hp[m]]>=val[hp[n]]){
break;
}
swap(hp[m],hp[n]);
swap(place[hp[m]],place[hp[n]]);
n=m;
}
}
void change(int n, T v){
T f = val[n];
val[n] = v;
if(place[n]==-1){
place[n] = size;
hp[size++] = n;
up(place[n]);
}
else{
if(f < v){
down(place[n]);
}
else if(f > v){
up(place[n]);
}
}
}
int pop(void){
int res = hp[0];
place[res] = -1;
size--;
if(size){
hp[0]=hp[size];
place[hp[0]]=0;
down(0);
}
return res;
}
}
;
template<class T> struct fenwick{
int size;
int memory;
T *data;
void malloc(int mem){
memory = mem;
data = (T*)std::malloc(sizeof(T)*mem);
}
void walloc(int mem, void **workMemory=&wmem){
memory = mem;
walloc1d(&data, mem, workMemory);
}
void free(void){
memory = 0;
free(data);
}
void init(int N){
size = N;
memset(data,0,sizeof(T)*N);
}
void add(int k, T val){
while(k < size){
data[k] += val;
k |= k+1;
}
}
T get(int k){
T res = 0;
while(k>=0){
res += data[k];
k = (k&(k+1))-1;
}
return res;
}
T range(int a, int b){
if(b==-1){
b=size-1;
}
return get(b) - get(a-1);
}
int kth(T k){
int i=0;
int j=size;
int c;
T v;
while(i<j){
c = (i+j)/2;
v = get(c);
if(v <= k){
i=c+1;
}
else{
j=c;
}
}
return i==size?-1:i;
}
}
;
struct graph{
int N;
int *es;
int **edge;
void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
int i;
N = N__;
walloc1d(&es, N, mem);
walloc1d(&edge, N, mem);
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
es[A[i]]++;
es[B[i]]++;
}
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], mem);
}
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 getDist(int root, int res[], void *mem = wmem){
int i;
int j;
int k;
int*q;
int s;
int z;
walloc1d(&q, N, &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;
}
}
}
int preorder(int res[], int root = 0, void *mem=wmem){
int i;
int j;
int k;
int *st;
int sts;
int sz = 0;
char *vis;
walloc1d(&vis, N, &mem);
walloc1d(&st, N, &mem);
sts = 0;
st[sts++] = root;
for(i=(0);i<(N);i++){
vis[i] = 0;
}
vis[root] = 1;
while(sts){
i = st[--sts];
res[sz++] = i;
for(j=(0);j<(es[i]);j++){
k = edge[i][j];
if(vis[k]){
continue;
}
vis[k] = 1;
st[sts++] = k;
}
}
return sz;
}
}
;
struct HLD{
int N;
int *es;
int **edge;
int *group;
int *groupind;
int groupNum;
int *groupSize;
int **groupNode;
int *groupUpNode;
int *groupDepth;
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){
int i;
int j;
int k;
int x;
int y;
int mx;
int *q;
int q_st;
int q_ed;
int *sz;
char *vis;
void *tmpmem;
N = N__;
es = es__;
edge = edge__;
walloc1d(&group, N, mem);
walloc1d(&groupind, N, mem);
tmpmem = *mem;
walloc1d(&q, N, &tmpmem);
walloc1d(&sz, N, &tmpmem);
walloc1d(&vis, N, &tmpmem);
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];
}
}
walloc1d(&groupSize, groupNum, mem);
walloc1d(&groupUpNode, groupNum, mem);
walloc1d(&groupDepth, groupNum, mem);
for(i=(0);i<(groupNum);i++){
groupSize[i] = 0;
}
for(i=(0);i<(N);i++){
groupSize[group[i]]++;
}
walloc1d(&groupNode, groupNum, mem);
for(i=(0);i<(groupNum);i++){
walloc1d(&groupNode[i], groupSize[i], mem);
}
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;
int y1;
int x2;
int 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 x1;
int x2;
int res = 0;
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 x1;
int y1;
int x2;
int y2;
int res = 0;
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];
int x2 = groupind[x];
if(x2==0){
return groupUpNode[x1];
}
return groupNode[x1][x2-1];
}
int up(int x, int d){
int x1 = group[x];
int 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_fenwick{
HLD *hld;
fenwick<T> *fen;
void init(HLD *hld__, void **mem = &wmem){
int i;
int j;
hld = hld__;
walloc1d(&fen, hld->groupNum, mem);
for(i=(0);i<(hld->groupNum);i++){
fen[i].walloc(hld->groupSize[i], mem);
fen[i].init(hld->groupSize[i]);
}
}
inline void add(int u, T val){
int ug;
int ui;
ug = hld->group[u];
ui = hld->groupind[u];
fen[ug].add(ui, val);
}
inline T get(int u, int v){
T res;
int ug;
int vg;
int ui;
int 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 += fen[ug].get(hld->groupind[u]);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
res += fen[ug].range(min_L(ui, vi),max_L(ui, vi));
return res;
}
}
;
int N;
int A[100000];
int B[100000];
int C[100000];
int sz;
int X[100000];
int dis[100001];
int pre[100000];
int val[100000];
int nx[100000];
int bf[100000];
int main(){
int KL2GvlyY;
wmem = memarr;
int i;
int j;
int k;
int m;
long long res;
graph g;
HLD hld;
HLD_fenwick<long long> t;
LHeap<int> hp;
rd(N);
{
int Lj4PdHRW;
for(Lj4PdHRW=(0);Lj4PdHRW<(N-1);Lj4PdHRW++){
rd(A[Lj4PdHRW]);
rd(B[Lj4PdHRW]);
rd(C[Lj4PdHRW]);
}
}
g.setEdge(N,N-1,A,B);
hld.init(g);
t.init(&hld);
hp.walloc(N);
g.getDist(0,dis);
dis[N] = -1073709056;
for(i=(0);i<(N-1);i++){
if(dis[A[i]] > dis[B[i]]){
swap(A[i], B[i]);
}
}
for(i=(0);i<(N-1);i++){
t.add(B[i], C[i]);
}
g.preorder(val);
for(i=(0);i<(N);i++){
pre[val[i]] = i;
}
int Q5VJL1cS = rd_int();
for(KL2GvlyY=(0);KL2GvlyY<(Q5VJL1cS);KL2GvlyY++){
int cTE1_r3A;
rd(sz);
{
int e98WHCEY;
for(e98WHCEY=(0);e98WHCEY<(sz);e98WHCEY++){
rd(X[e98WHCEY]);
}
}
for(i=(0);i<(sz);i++){
val[i] = pre[X[i]];
}
sortA_L(sz, val, X);
hp.init(sz-1);
for(i=(0);i<(sz-1);i++){
k = hld.lca(X[i],X[i+1]);
hp.change(i, -dis[k]);
}
for(i=(0);i<(sz);i++){
bf[i] = i-1;
}
for(i=(0);i<(sz);i++){
nx[i] = i+1;
}
res = 0;
for(cTE1_r3A=(0);cTE1_r3A<(sz-1);cTE1_r3A++){
i = hp.pop();
j = nx[i];
k = hld.lca(X[i], X[j]);
res += t.get(X[i], k) - t.get(k,k);
res += t.get(X[j], k) - t.get(k,k);
X[j] = k;
k = bf[j] = bf[i];
if(k >= 0){
nx[k] = j;
}
if(0 <= j && j < sz-1 && 0 <= nx[j] && nx[j] < sz){
m = hld.lca(X[j], X[nx[j]]);
hp.change(j, -dis[m]);
}
if(0 <= k && k < sz-1 && 0 <= nx[k] && nx[k] < sz){
m = hld.lca(X[k], X[nx[k]]);
hp.change(k, -dis[m]);
}
}
wt_L(res);
wt_L('\n');
}
return 0;
}
// cLay varsion 20190929-1
// --- original code ---
// int N, A[1d5], B[1d5], C[1d5];
// int sz, X[1d5];
// int dis[100001], pre[1d5], val[1d5];
//
// int nx[1d5], bf[1d5];
//
// {
// int i, j, k, m;
// ll res;
// graph g;
// HLD hld;
// HLD_fenwick<ll> t;
// LHeap<int> hp;
//
// rd(N,(A,B,C)(N-1));
//
// g.setEdge(N,N-1,A,B);
// hld.init(g);
// t.init(&hld);
// hp.walloc(N);
//
// g.getDist(0,dis);
// dis[N] = -int_inf;
// rep(i,N-1) if(dis[A[i]] > dis[B[i]]) swap(A[i], B[i]);
// rep(i,N-1) t.add(B[i], C[i]);
//
// g.preorder(val);
// rep(i,N) pre[val[i]] = i;
//
// REP(rd_int()){
// rd(sz,X(sz));
// rep(i,sz) val[i] = pre[X[i]];
// sortA(sz, val, X);
// hp.init(sz-1);
// rep(i,sz-1){
// k = hld.lca(X[i],X[i+1]);
// hp.change(i, -dis[k]);
// }
// rep(i,sz) bf[i] = i-1;
// rep(i,sz) nx[i] = i+1;
// res = 0;
// rep(sz-1){
// i = hp.pop();
// j = nx[i];
// k = hld.lca(X[i], X[j]);
// res += t.get(X[i], k) - t.get(k,k);
// res += t.get(X[j], k) - t.get(k,k);
// X[j] = k;
// k = bf[j] = bf[i];
// if(k >= 0) nx[k] = j;
// if(0 <= j < sz-1 && 0 <= nx[j] < sz){
// m = hld.lca(X[j], X[nx[j]]);
// hp.change(j, -dis[m]);
// }
// if(0 <= k < sz-1 && 0 <= nx[k] < sz){
// m = hld.lca(X[k], X[nx[k]]);
// hp.change(k, -dis[m]);
// }
// }
// wt(res);
// }
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0