QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107180 | #5313. Please Save Pigeland | shihoghmean | WA | 20ms | 29420kb | C++14 | 3.2kb | 2023-05-20 15:26:25 | 2023-05-20 15:26:26 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'