QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#315761#4433. Kitten and RoombalinlexiaoRE 7407ms120180kbC++203.0kb2024-01-27 15:42:002024-01-27 15:42:00

Judging History

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

  • [2024-01-27 15:42:00]
  • 评测
  • 测评结果:RE
  • 用时:7407ms
  • 内存:120180kb
  • [2024-01-27 15:42:00]
  • 提交

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);

        a /= (sz[x]+(fa[x]!=0));

        if(sz[x])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: 7407ms
memory: 120180kb

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: 277ms
memory: 12112kb

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...

output:


result: