QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#319069 | #5313. Please Save Pigeland | peter | WA | 3ms | 31240kb | C++14 | 3.6kb | 2024-02-01 18:45:03 | 2024-02-01 18:45:04 |
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>
#define int long long
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],vc[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==-1) return x;
if(x.first==-1) 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 %lld\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){
if(!num[u]) gg[u].first=-1;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==ff) continue;
dfs3(v,u);
if(num[v]){
pii tmp=gg[v];
tmp.first+=e[i].d;
// printf("kk%d %lld %lld %lld\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%lld %lld %lld\n",u,gg[u].first,gg[u].second);
}
void dfs4(int u,int ff,pii val){
dp[u]=gg[u]+val;
// printf("%lld %lld %lld %lld %lld\n",u,fz[u],dp[u].first,dp[u].second,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 %lld\n",u,v);
vec[u].push_back(make_pair(v,e[i].d));
}
pre[0]=suf[(int)vec[u].size()+1]=make_pair(-1,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("%lld %lld\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];
if(bk[u]){
if(tmp.first==-1) tmp.first=0;
tmp.first+=vec[u][i].second;
tmp.second=gcd(tmp.second,tmp.first);
}else{
if(tmp.first!=-1) tmp.first+=vec[u][i].second;
}
// printf("kk%lld %lld %lld %lld\n",u,vec[u][i].first,tmp.first,tmp.second);
vc[u].push_back(tmp);
}
for(int i=0;i<(int)vec[u].size();i++) dfs4(vec[u][i].first,u,vc[u][i]);
}
signed main(){
init();
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;i++){
int x;
scanf("%lld",&x);
num[x]++;
bk[x]=1;
}
for(int i=1;i<n;i++){
int u,v,d;
scanf("%lld %lld %lld",&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 %lld\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(-1,0));
printf("%lld\n",res);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 31240kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
2
result:
wrong answer 1st numbers differ - expected: '8', found: '2'