QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107180#5313. Please Save PigelandshihoghmeanWA 20ms29420kbC++143.2kb2023-05-20 15:26:252023-05-20 15:26:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 15:26:26]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:29420kb
  • [2023-05-20 15:26:25]
  • 提交

answer

// Problem: M. Please Save Pigeland
// Contest: Codeforces - The 2022 ICPC Asia Hangzhou Regional Programming Contest
// URL: https://codeforces.com/gym/104090/problem/M
// Memory Limit: 1024 MB
// Time Limit: 3000 ms

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i--)
#define py puts("Yes")
#define pn puts("No")
#define pt puts("")
#define pb push_back
#define wt(x) write(x),puts("")
#define wr(x) write(x) ,putchar(' ')
#define tx printf("fds")
#define mp make_pair
#define fi first
#define se second
inline int read(){
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*k;
}
void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int power(int x,int y,int mod){
	int num=1;
	while(y){
		if(y&1) num=(num*x)%mod;
		x=x*x%mod;
		y>>=1;
	}
	return num;
}
int mul(int x,int y,int mod){
	int num=0;
	while(y){
		if(y&1) num=(num+x)%mod;
		x=(x+x)%mod;
		y>>=1;
	}
	return num;
}
const int N=1e6+7,mod=998244353;
int n,m,tot,cnt,ans,k,ppp;
int a[N],b[N],vis[N],val[N];
int head[N];
struct edge{
	int to,next,val;
}e[N];
void add(int u,int v,int val){
	e[++tot]={v,head[u],val};
	head[u]=tot;
}
int siz[N],fa[N],nm[N],L[N],dfn[N];
void dfs(int u,int f,int dep){
	fa[u]=f;
	a[u]=dep;
	if(vis[u]) siz[u]=1,ppp+=dep;
	if(vis[u]) dfn[u]=++cnt,nm[cnt]=u,L[u]=cnt;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==f) continue;
		dfs(v,u,dep+e[i].val);
		L[u]=min(L[u],L[v]);
		siz[u]+=siz[v];
	}
}
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
struct tree{
	int num;
}t[N];
void pu(int id){
	t[id].num=gcd(abs(t[id<<1].num),abs(t[id<<1|1].num));
}
void build(int id,int l,int r){
	if(l==r){
		if(l==1) t[id].num=a[nm[l]];
		else t[id].num=a[nm[l]]-a[nm[l-1]];
		// printf("%d %d %d\n",id,l,t[id].num); 
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	pu(id);
}
void update(int id,int l,int r,int x,int k){
	if(l==r){
		t[id].num+=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(id<<1,l,mid,x,k);
	else update(id<<1|1,mid+1,r,x,k);
	pu(id);
}
void solve(int u,int f,int num){
	if(t[1].num!=0) 
	ans=min(ans,num/t[1].num);
	// printf("%d %d %d\n",u,num,t[1].num);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==f) continue;
		int x=L[v];
		int y=x+siz[v]-1;
		int o=num;
		o-=(y-x+1)*e[i].val;
		o+=(m-y+x-1)*e[i].val;
		update(1,1,m,1,e[i].val);
		if(x<=y)update(1,1,m,x,-2*e[i].val);
		if(y!=m&&x<=y)update(1,1,m,y+1,2*e[i].val);
		solve(v,u,o);
		update(1,1,m,1,-e[i].val);
		if(x<=y)update(1,1,m,x,2*e[i].val);
		if(y!=m&&x<=y) update(1,1,m,y+1,-2*e[i].val);
	}
}
signed main(){
	n=read();m=read();
	fo(i,1,n) L[i]=1e9;
	fo(i,1,m){
		int x=read();
		vis[x]=1;
	}
	fo(i,2,n){
		int x=read(),y=read(),z=read();
		add(x,y,z);
		add(y,x,z);
	}
	ans=1e9;
	dfs(1,0,0);
	build(1,1,m);
	solve(1,0,ppp);
	if(ans==1e9) wt(0);
	else wt(ans*2);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 19700kb

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: 2ms
memory: 19740kb

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: 1ms
memory: 17636kb

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 20ms
memory: 29420kb

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:

2

result:

wrong answer 1st numbers differ - expected: '0', found: '2'