QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#346098 | #4433. Kitten and Roomba | studentDL | WA | 459ms | 46884kb | C++14 | 2.1kb | 2024-03-07 20:30:36 | 2024-03-07 20:30:37 |
Judging History
answer
#include<algorithm>
#include<cstdio>
#include<cstring>
#define pii pair<int,int>
#define mk make_pair
#define ft first
#define se second
#define pb push_back
#define db double
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define inf 1e18
using namespace std;
namespace IO{
#ifndef LOCAL
#define SIZE 30000
char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(p3=out,1,SIZE,stdout))
#define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
class Flush{public:~Flush(){fwrite(out,1,p3-out,stdout);}}_;
#endif
template<typename type>
inline void read(type &x){
x=0;bool flag=0;char ch=getchar();
while(ch<'0'||ch>'9') flag^=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x,char ch=0){
x<0?x=-x,putchar('-'):0;static short Stack[50],top=0;
do Stack[++top]=x%10,x/=10;while(x);
while(top) putchar(Stack[top--]|48);
if(ch) putchar(ch);
}
}
using namespace IO;
#define M 1000005
int n,m,ini,cnt,head[M];
struct edge{
int nxt,v;
}e[M<<1];
void add(int u,int v){
e[++cnt]={head[u],v};
head[u]=cnt;
}
int fa[M],deg[M];
void dfs(int u,int f){
fa[u]=f;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==f) continue;
dfs(v,u);
deg[u]++,deg[v]++;
}
}
db ans,dp[M],tag[M];
void solve(){
read(n),read(ini);
cnt=ans=0;
for(int i=1;i<=n;i++) head[i]=deg[i]=dp[i]=tag[i]=0;
dp[ini]=1;
for(int i=1,u,v;i<n;i++){
read(u),read(v);
add(u,v),add(v,u);
}
dfs(1,0);
read(m);
for(int i=1,u;i<=m;i++){
read(u);
dp[u]+=tag[fa[u]],ans+=dp[u];
dp[fa[u]]+=dp[u]/deg[u];
tag[u]+=dp[u]/deg[u],dp[u]=0;
}
printf("%.10lf\n",ans);
}
int main(){
int T;read(T);
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 459ms
memory: 46884kb
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:
60282889699681741987864091585727204431172217290543693464099825135249797010662119913376610263992338434642621212511108530841068744154522075624669964560760320351599314247938451032368598265374681786266700818653030383616.0000000000 6019957012853342831080099435258636911400567104858162428068140589163116746...
result:
wrong answer 1st numbers differ - expected: '5.60942', found: '60282889699681741987864091585727204431172217290543693464099825135249797010662119913376610263992338434642621212511108530841068744154522075624669964560760320351599314247938451032368598265374681786266700818653030383616.00000', error = '1074...