QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276749 | #4159. 消耗战 | SoyTony | 100 ✓ | 251ms | 60736kb | C++14 | 5.2kb | 2023-12-06 10:17:14 | 2023-12-06 10:17:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=25e4+10;
const int maxm=2e6+10;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int n,m;
struct Tree{
struct edge{
int v,w;
edge()=default;
edge(int v_,int w_):v(v_),w(w_){}
};
vector<edge> E[maxn];
inline void add_edge(int u,int v,int w){
E[u].push_back(edge(v,w));
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int dfn[maxn],dfncnt,top[maxn];
int mn[maxn][18];
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,siz[u]=1;
int maxson=-1;
for(edge e:E[u]){
int v=e.v,w=e.w;
if(v==f) continue;
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson) son[u]=v,maxson=siz[v];
}
}
void dfs2(int u,int t){
dfn[u]=++dfncnt,top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(edge e:E[u]){
int v=e.v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void dfs3(int u){
for(edge e:E[u]){
int v=e.v,w=e.w;
if(v==fa[u]) continue;
mn[dfn[v]][0]=w;
dfs3(v);
}
}
inline void build_mn(){
mn[1][0]=0x3f3f3f3f;
dfs3(1);
for(int k=1;k<=17;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
mn[i][k]=min(mn[i][k-1],mn[i+(1<<k-1)][k-1]);
}
}
}
inline int query_mn(int l,int r){
int k=log2(r-l+1);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline int get_LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
inline int get_mn(int u,int v){
int res=0x3f3f3f3f;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
res=min(res,query_mn(dfn[top[v]],dfn[v]));
v=fa[top[v]];
//printf("uv:%d %d %d\n",u,v,res);
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) res=min(res,query_mn(dfn[u]+1,dfn[v]));
return res;
}
int id[maxn];
bool mark[maxn];
int st[maxn],tp;
struct EDGE{
int to,w,nxt;
}e[maxm];
int head[maxn],cnt;
inline void add_EDGE(int u,int v,int w){
e[++cnt].to=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}
inline void build(){
tp=0,st[++tp]=1,st[++tp]=id[1];
head[1]=head[id[1]]=0;
for(int i=2;i<=id[0];++i){
int u=id[i];
//找到第一个次栈顶深度小于等于LCA的
//printf("%d %d %d %d\n",u,st[tp],get_LCA(u,st[tp]),st[tp-1]);
if(get_LCA(u,st[tp])==st[tp]){
st[++tp]=u;
head[u]=0;
continue;
}
while(tp>1&&dep[get_LCA(u,st[tp])]<dep[st[tp-1]]){
add_EDGE(st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
//printf("%d %d %d\n",st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
--tp;
}
//LCA已然入栈
if(get_LCA(u,st[tp])==st[tp-1]){
head[u]=0;
add_EDGE(st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
//printf("%d %d %d\n",st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
st[tp]=u;
}
else{
int lca=get_LCA(u,st[tp]);
head[lca]=0,head[u]=0;
add_EDGE(lca,st[tp],get_mn(lca,st[tp]));
//printf("%d %d %d\n",lca,st[tp],get_mn(lca,st[tp]));
st[tp]=lca,st[++tp]=u;
}
/*for(int i=head[1];i;i=e[i].nxt) printf("%d ",e[i].to);
printf("\n");*/
}
while(tp>1){
add_EDGE(st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
//printf("%d %d %d\n",st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
--tp;
}
}
ll dp[maxn];
void dfs(int u){
dp[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
//printf("%d->%d %d\n",u,v,w);
dfs(v);
if(mark[v]) dp[u]+=w;
else dp[u]+=min(dp[v],(ll)w);
}
}
inline void solve(){
id[0]=read();
for(int i=1;i<=id[0];++i) mark[id[i]=read()]=1;
sort(id+1,id+id[0]+1,[&](int x,int y){
return dfn[x]<dfn[y];
});
build();
dfs(1);
printf("%lld\n",dp[1]);
for(int i=1;i<=id[0];++i) mark[id[i]]=0;
}
}T;
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read(),w=read();
T.add_edge(u,v,w);
T.add_edge(v,u,w);
}
T.dfs1(1,0,0);
T.dfs2(1,1);
T.build_mn();
/*for(int i=1;i<=n;++i){
printf("u:%d dfn:%d top:%d\n",i,T.dfn[i],T.top[i]);
}*/
m=read();
while(m--){
T.solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 0ms
memory: 19492kb
input:
100 1 2 3872 2 3 2287 2 4 2427 2 5 7759 1 6 2695 5 7 9472 6 8 1299 1 9 4637 8 10 2386 4 11 4623 10 12 5610 5 13 891 2 14 143 5 15 3363 14 16 3490 1 17 6588 14 18 2877 13 19 68 3 20 1702 17 21 700 21 22 5439 11 23 7487 22 24 2996 13 25 8201 23 26 7510 23 27 2657 26 28 5831 5 29 9863 16 30 8873 2 31 9...
output:
7267 3444 3872 727 6191 10128 7267 6191 3872 3747 5992 3011 143 2427 3872 10508 4892 5171 5171 569 6567 6567 3498 5171 6567 10828 5491 3872 3872 4572 5740 9650 8988 4192 3872 3039 1997 700 10460 2190 6887 5171 1139 9398 3726 8290 1087 6060 4693 6567 10460 7267 874 5171 4572 6046 6887 3872 3363 4161 ...
result:
ok 100 lines
Test #2:
score: 10
Accepted
time: 37ms
memory: 25428kb
input:
1000 1 2 537 1 3 2059 1 4 8586 3 5 5724 3 6 8019 1 7 6286 1 8 3653 2 9 3684 4 10 6654 4 11 4488 4 12 7127 11 13 2066 11 14 7876 5 15 6664 8 16 8598 14 17 5744 15 18 3807 1 19 1351 19 20 662 13 21 3559 13 22 7508 2 23 3181 7 24 2384 21 25 3849 13 26 618 11 27 5810 24 28 4856 7 29 6843 21 30 4627 5 31...
output:
2728 2910 3824 2431 4459 7429 4827 1519 2431 3166 4339 4016 3042 5086 4125 2803 1502 2587 1920 1567 769 684 999 2575 2909 1677 1756 1155 792 2066 4020 4506 2222 363 1280 3672 3325 2728 662 1280 900 379 2106 4016 2129 4634 707 2721 2929 1849 4315 1280 848 2685 2059 2603 1406 618 4432 2544 1908 2596 1...
result:
ok 166666 lines
Test #3:
score: 10
Accepted
time: 47ms
memory: 26488kb
input:
1000 1 2 2564 1 3 1499 1 4 9826 2 5 5515 1 6 8014 2 7 638 1 8 3916 6 9 1976 3 10 8803 5 11 5933 10 12 3738 11 13 3448 10 14 9249 10 15 867 3 16 1237 8 17 3322 5 18 1794 1 19 7298 9 20 9216 9 21 3952 8 22 5296 1 23 9836 18 24 9160 2 25 6225 7 26 4424 5 27 3818 9 28 2152 4 29 6383 27 30 1505 13 31 413...
output:
2564 113 2485 501 2799 2757 5691 1499 2211 3844 4190 2901 1530 726 2564 5229 5536 2813 2743 857 2776 638 1587 2169 3519 10299 3143 1195 1961 2564 2137 2564 5275 2564 2711 1107 1555 8301 829 1772 6884 3671 2137 3770 2564 2564 1680 3801 313 3113 1496 2933 3671 2564 1910 5554 4063 2477 3083 4063 3221 3...
result:
ok 250000 lines
Test #4:
score: 10
Accepted
time: 217ms
memory: 60736kb
input:
250000 1 2 2268 1 3 3908 3 4 8278 4 5 4693 4 6 3931 5 7 2207 4 8 9819 7 9 2678 1 10 2206 3 11 433 2 12 7081 4 13 179 2 14 3770 13 15 1328 4 16 1167 10 17 3542 2 18 6968 9 19 5150 12 20 692 14 21 6096 4 22 4619 22 23 3564 23 24 801 6 25 4668 25 26 3824 18 27 3190 8 28 3064 17 29 1159 20 30 4957 23 31...
output:
11933 20150 13672 10226 9037 12030 14820 12212 11170 8490 14559 12157 12598 20332 12625 19691 13141 11319 13118 10386 11224 12343 10561 13672 13006 8748 13672 13672 11381 9626 8403 13672 10155 19619 13068 11782 11067 15861 9402 13672 13672 12118 15496 9158 12625 11842 19339 11284 8710 13653 9368 136...
result:
ok 5000 lines
Test #5:
score: 10
Accepted
time: 251ms
memory: 58744kb
input:
250000 1 2 6901 1 3 6877 3 4 4119 4 5 8363 1 6 9998 3 7 6589 3 8 9451 4 9 2328 1 10 1612 7 11 6154 8 12 1583 3 13 6664 7 14 924 8 15 9077 15 16 9191 11 17 1997 7 18 1879 13 19 9237 2 20 1222 19 21 6336 7 22 8576 12 23 8169 16 24 4638 1 25 8765 19 26 4484 11 27 6850 9 28 2985 20 29 657 29 30 4817 9 3...
output:
22470 16304 14462 11066 13700 13826 15177 11114 8911 14623 12886 16744 12731 8553 19666 13797 14211 12747 10918 11989 12280 10424 18039 8931 15555 17003 12569 17133 14638 11317 11180 10622 14142 10475 9214 22966 8192 11779 13180 10206 12513 10714 14555 13952 16398 18370 19955 20313 17191 10625 11110...
result:
ok 16666 lines
Test #6:
score: 10
Accepted
time: 196ms
memory: 58908kb
input:
250000 38777 108274 87589 108274 160854 77640 160854 60552 78805 60552 200039 58017 200039 84497 69330 84497 124673 34582 124673 58879 30083 58879 212671 64495 212671 36027 38890 36027 101232 26550 101232 191826 77803 191826 86159 43383 86159 10737 29218 10737 169665 79625 169665 215204 9275 215204 ...
output:
694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 437 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 694 ...
result:
ok 9891 lines
Test #7:
score: 10
Accepted
time: 196ms
memory: 57456kb
input:
250000 28712 5893 24269 5893 234660 76106 234660 68804 34449 68804 92158 10190 92158 30430 94629 30430 147323 97917 147323 3900 76522 3900 163904 33184 163904 230315 6988 230315 84092 49596 84092 228686 22214 228686 34943 64054 34943 156088 9160 156088 40788 8540 40788 214979 48213 214979 90403 7986...
output:
531 531 531 531 531 531 531 531 531 361 531 531 531 531 531 531 531 531 531 531 531 481 531 531 531 531 531 531 438 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 531 ...
result:
ok 62334 lines
Test #8:
score: 10
Accepted
time: 247ms
memory: 57964kb
input:
250000 1 2 3705 2 3 3084 3 4 8957 3 5 5735 1 6 1597 6 7 3523 5 8 1769 7 9 8021 8 10 8743 5 11 3445 9 12 2611 4 13 5966 11 14 4466 4 15 830 7 16 6111 7 17 9587 11 18 2402 2 19 178 15 20 5660 16 21 5340 9 22 4499 7 23 65 14 24 1874 16 25 3921 17 26 1203 22 27 8893 27 28 9215 4 29 4481 1 30 5282 14 31 ...
output:
5913 5302 4681 4647 6272 6725 8785 4681 3437 4347 4681 4851 4681 4184 4681 5302 4849 6116 1930 5393 5616 5959 4840 5385 4681 4681 4681 4681 5381 4853 5033 4049 4082 5302 5497 4681 2817 4332 6277 8364 3349 7342 4737 4176 4859 5854 4646 5912 6167 4859 5555 7050 5097 4711 8206 9405 4112 5075 5521 4681 ...
result:
ok 50000 lines
Test #9:
score: 10
Accepted
time: 147ms
memory: 52864kb
input:
250000 1 156736 100000 156736 146447 100000 146447 238841 100000 1 91578 100000 1 181978 100000 1 248425 100000 1 134840 100000 134840 230020 100000 230020 245935 100000 1 218596 100000 218596 139329 100000 1 130973 100000 130973 155892 100000 1 44564 100000 44564 40236 100000 1 123733 100000 123733...
output:
11877300000 12066100000 1128400000 3397000000 78000000 57600000 231800000 201200000 51600000 7300000 100000 600000 300000 100000
result:
ok 14 lines
Test #10:
score: 10
Accepted
time: 0ms
memory: 20172kb
input:
10 1 2 6432 2 3 9694 3 4 9714 4 5 8890 4 6 9170 1 7 6361 1 8 1627 2 9 9824 7 10 9947 5 3 4 7 2 5 7 2 10 6 3 5 3 7 4 8 10 3 3 2 10 2 6 8
output:
12793 12793 14420 12793 8059
result:
ok 5 lines