QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#315833 | #4433. Kitten and Roomba | linlexiao | RE | 7684ms | 118948kb | C++20 | 3.1kb | 2024-01-27 16:02:22 | 2024-01-27 16:02:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;using i128=__int128_t;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__)
#define endl '\n'
#define pb push_back
inline int read(){int f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
template <class T> inline T read(){T f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
template <class T> void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
using ld=double;
const int N = 1e6+5;
vector<int> G[N];
int fa[N],bdfn[N],sz[N],st[N];
int tot;
struct Node{
ld a;
ld taga;
}t[N*4];
void pushup(int o){
t[o].a=t[o<<1].a+t[o<<1|1].a;
}
void upd(int o,int l,int r,ld qa){
t[o].a+=qa*(r-l+1),t[o].taga+=qa;
}
void build(int o,int l,int r){
t[o]={0,0};
if(l==r)return;
int lch=o<<1,rch=o<<1|1;
int mid=(l+r)>>1;
build(lch,l,mid),build(rch,mid+1,r);
}
void pushdown(int o,int l,int r){
if(t[o].taga){
int mid=(l+r)>>1;
upd(o<<1,l,mid,t[o].taga);
upd(o<<1|1,mid+1,r,t[o].taga);
t[o].taga=0;
}
}
void add(int o,int l,int r,int ql,int qr,ld qa){
if(ql>qr)return;
if(ql<=l&&r<=qr)return upd(o,l,r,qa);
pushdown(o,l,r);
int lch=o<<1,rch=o<<1|1;
int mid=(l+r)>>1;
if(ql<=mid)add(lch,l,mid,ql,qr,qa);
if(qr>mid)add(rch,mid+1,r,ql,qr,qa);
pushup(o);
}
ld query(int o,int l,int r,int qi){
if(qi<l || qi>r)return 0;
if(l==r)return t[o].a;
pushdown(o,l,r);
int lch=o<<1,rch=o<<1|1;
int mid=(l+r)>>1;
if(qi<=mid)return query(lch,l,mid,qi);
return query(rch,mid+1,r,qi);
}
void bdfs(int u,int f){
fa[u]=f;
for(int v:G[u]){
if(v==f)continue;
bdfn[v]=++tot;
if(!st[u])st[u]=tot;
sz[u]++;
}
for(int v:G[u]){
if(v==f)continue;
bdfs(v,u);
}
}
void solve(){
int n=read(),c=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
G[u].push_back(v);G[v].push_back(u);
}
tot=1;bdfn[1]=1;
bdfs(1,0);
build(1,1,n);
add(1,1,n,bdfn[c],bdfn[c],1);
int m=read();
ld ans = 0;
for(int i=1;i<=m;i++){
int x=read();
auto a = query(1,1,n,bdfn[x]);
ans += a;
add(1,1,n,bdfn[x],bdfn[x],-a);
if(sz[x] + (fa[x]!=0) == 0){
return;
}
a /= (sz[x]+(fa[x]!=0));
if(sz[x]){
if(!st[x])return;
add(1,1,n,st[x],st[x]+sz[x]-1,a);
}
if(fa[x])add(1,1,n,bdfn[fa[x]],bdfn[fa[x]],a);
}
for(int i=1;i<=n;i++)G[i].clear(),sz[i]=0;
printf("%.8f\n",ans);
}
int main(){
int T=read();
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7684ms
memory: 118948kb
input:
2 1000000 315562 969409 917725 324847 719085 524235 603427 576843 433171 75335 238378 266746 487233 80422 95099 594363 96140 858172 261406 958326 466109 233845 350950 863969 345645 689972 81395 395383 27274 93913 208983 523722 380358 108074 172341 130041 692304 737158 383812 752080 33646 154356 6672...
output:
5.60941734 5.61050514
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 275ms
memory: 3828kb
input:
3 3 3 2 1 2 3 4000000 2 1 2 1 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 1 2 3 2 3 2 1 2 3 2 3 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 1 2 3 2 3 2 1 2 3 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 1 2 ...
output:
2000496.59736927 4999999.00000000 666788.77808048
result:
ok 3 numbers
Test #3:
score: -100
Runtime Error
input:
5050 178 146 7 29 45 132 140 19 48 80 50 147 24 98 176 94 45 124 3 161 36 94 4 33 24 81 94 123 4 15 12 170 152 95 55 152 24 131 94 32 121 150 37 167 146 80 65 152 99 150 24 60 8 29 5 163 64 50 93 67 19 13 24 153 80 152 29 120 67 59 138 48 5 17 19 35 94 116 57 142 80 53 6 45 29 80 150 40 47 161 62 94...