QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#319060 | #5313. Please Save Pigeland | peter | RE | 3ms | 29916kb | C++14 | 3.2kb | 2024-02-01 18:13:41 | 2024-02-01 18:13:41 |
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;
// 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;
res=min(res,fz[u]/gcd(dp[u].first,dp[u].second)*2);
// printf("%d %d %d\n",u,fz[u],gcd(dp[u].first,dp[u].second));
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: 0ms
memory: 28856kb
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: 3ms
memory: 29916kb
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: -100
Runtime Error
input:
1 1 1