QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#319062 | #5313. Please Save Pigeland | peter | WA | 17ms | 20552kb | C++14 | 3.2kb | 2024-02-01 18:15:42 | 2024-02-01 18:15:43 |
Judging History
answer
// Problem: qoj5313 Please Save Pigeland
// Contest: Qoj
// URL: https://qoj.ac/problem/5313
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e5+5;
typedef pair<int,int> pii;
int num[maxn],fz[maxn],n,m;
struct edge{
int to,nxt,d;
}e[maxn<<1];
int head[maxn],len,res=inf,all=0;
bool bk[maxn];
pii gg[maxn],dp[maxn];
pii pre[maxn],suf[maxn];
vector<pii> vec[maxn];
int gcd(int x,int y){
if(y==0) return x;
return gcd(y,x%y);
}
pii operator + (pii x,pii y){
if(y.first==0&&y.second==0) return x;
// if(x.first==0&&x.second==0) return y;
return make_pair(x.first,gcd(gcd(x.second,y.second),abs(x.first-y.first)));
}
inline void init(){
memset(head,-1,sizeof(head));
len=0;
}
void add(int u,int v,int d){
e[++len].to=v;
e[len].d=d;
e[len].nxt=head[u];
head[u]=len;
}
void dfs1(int u,int f){
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u);
num[u]+=num[v];
all+=num[v]*e[i].d;
}
}
void dfs2(int u,int f,int val){
fz[u]=val;
if(val==0){
puts("0");
exit(0);
}
// printf("kk%d %d\n",u,fz[u]);
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs2(v,u,val-num[v]*e[i].d+(m-num[v])*e[i].d);
}
}
void dfs3(int u,int ff){
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==ff||(!num[v])) continue;
if(num[v]) dfs3(v,u);
pii tmp=gg[v];
tmp.first+=e[i].d;
// printf("kk%d %d %d %d\n",u,v,tmp.first,tmp.second);
if(gg[u].first==0&&gg[u].second==0&&(!bk[u])) gg[u]=tmp;
else gg[u]=gg[u]+tmp;
}
// printf("kk%d %d %d\n",u,gg[u].first,gg[u].second);
}
void dfs4(int u,int ff,pii val){
dp[u]=gg[u]+val;
// printf("%d %d %d\n",u,fz[u],gcd(dp[u].first,dp[u].second));
// exit(0);
res=min(res,fz[u]/gcd(dp[u].first,dp[u].second)*2);
vec[u].clear();
// vec.push_back(make_pair(0,0));
for(int i=head[u],j=1;i!=-1;i=e[i].nxt,j++){
int v=e[i].to;
if(v==ff) continue;
// printf("kk%d %d\n",u,v);
vec[u].push_back(make_pair(v,e[i].d));
}
pre[0]=suf[(int)vec[u].size()+1]=make_pair(0,0);
for(int i=0;i<(int)vec[u].size();i++){
pii tmp=gg[vec[u][i].first];
tmp.first+=vec[u][i].second;
pre[i+1]=pre[i]+tmp;
}
for(int i=(int)vec[u].size()-1;i>=0;i--){
pii tmp=gg[vec[u][i].first];
tmp.first+=vec[u][i].second;
suf[i+1]=suf[i+2]+tmp;
}
// printf("kk%d\n",u);
// for(int i=0;i<(int)vec[u].size();i++) printf("%d %d\n",pre[i+1].first,pre[i+1].second);
for(int i=0;i<(int)vec[u].size();i++){
pii tmp=val+pre[i]+suf[i+2];
tmp.first+=vec[u][i].second;
// printf("kk%d %d %d\n",vec[u][i].first,tmp.first,tmp.second);
dfs4(vec[u][i].first,u,tmp);
}
}
int main(){
init();
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);
num[x]++;
bk[x]=1;
}
for(int i=1;i<n;i++){
int u,v,d;
scanf("%d %d %d",&u,&v,&d);
add(u,v,d);
add(v,u,d);
}
// pii tmp=make_pair(3,6),tmp2=make_pair(6,9),tmp3=tmp+tmp2;
// printf("kkk%d %d\n",tmp3.first,tmp3.second);
dfs1(1,0);
// printf("kk%d\n",all);
dfs2(1,0,all);
dfs3(1,0);
// exit(0);
dfs4(1,0,make_pair(0,0));
printf("%d\n",res);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 17636kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 17440kb
input:
10 3 1 7 10 7 6 3 1 8 3 3 6 3 8 6 2 4 1 1 10 6 4 2 8 3 9 10 3 5 10 3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: 0
Accepted
time: 8ms
memory: 17344kb
input:
1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 17ms
memory: 20552kb
input:
100000 1 79187 72704 72659 15 32741 43496 10 21580 97447 17 55758 36700 21 32116 3643 14 60460 58764 12 75894 50624 7 58295 49393 22 43733 17210 1 58093 68769 15 1086 58916 17 25632 37710 11 49555 92976 8 32547 27060 18 84896 12811 1 3196 1242 16 18870 78236 14 2414 7945 12 48745 15399 1 17648 83791...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 3ms
memory: 17444kb
input:
100 10 3 27 33 45 48 72 76 91 92 100 66 98 4 70 17 2 28 59 4 26 25 3 77 92 1 40 61 2 11 27 2 85 35 1 57 26 1 68 99 4 50 84 1 20 82 3 31 39 1 71 7 4 54 55 4 60 26 4 56 61 2 15 66 3 95 53 2 8 60 4 21 82 1 18 81 2 29 73 3 94 4 1 10 4 4 86 43 1 62 41 1 45 57 1 25 66 3 69 89 2 14 53 3 27 92 1 42 98 4 13 ...
output:
200
result:
ok 1 number(s): "200"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 17448kb
input:
100 90 75 17 78 84 52 69 54 24 74 35 58 51 72 7 21 70 93 15 60 87 13 40 23 92 99 53 27 22 91 46 56 86 61 19 44 98 50 28 14 12 55 64 30 80 95 38 18 43 31 89 20 16 8 65 63 79 59 34 97 25 2 11 67 71 29 9 37 76 77 26 39 68 32 62 90 10 85 49 42 45 96 83 94 3 6 100 81 57 88 47 67 65 1 43 78 4 98 71 3 71 2...
output:
1728
result:
wrong answer 1st numbers differ - expected: '1798', found: '1728'