QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#65206 | #4433. Kitten and Roomba | AmrMohameD | TL | 0ms | 0kb | C++ | 3.7kb | 2022-11-28 02:04:58 | 2022-11-28 02:05:02 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sc second
#define EPS 1e-9
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define EPS 1e-9
#define PI acos(-1.0)
#define ll long long
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pb push_back
#define ft first
#define sc second
#define pi pair<ll,ll>
#define vi vector<ll>
#define sz(s) s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll N = 1e6+5, M = 300 + 5, MOD = 1e4+5, INF = 1e18;
int dx[] = {-1, 1, 0, 0}, Dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};;
int dy[] = {0, 0, 1, -1}, Dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, tt, ID[N], timer, mx[N],p[N];
vi g[N];
long double seg[N*4], lazy[N*4];
void bfs(int s)
{
queue<int> q;
q.push(s);
ID[s] = ++timer;
while(sz(q))
{
int node = q.front(); q.pop();
for(auto it:g[node])
{
if(!ID[it]){
ID[it] = ++timer;
q.push(it);
p[it]= node;
}
}
}
}
void dfs(int s,int p)
{
int tmp = ID[s];
for(auto it:g[s])
{
tmp = max(tmp,ID[it]);
}
mx[s] = tmp;
for(auto it:g[s])
{
if(it != p)
{
dfs(it,s);
}
}
}
void check(int v,int l,int r)
{
if(lazy[v]>EPS)
{
seg[v] += lazy[v];
if(l != r){
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
}
lazy[v] = 0;
}
}
void update(int v,int l,int r,int s,int e,long double val)
{
check(v,l,r);
if(l >= s && r <= e)
{
if(s == e) lazy[v] = val;
else lazy[v] += val;
check(v,l,r);
return;
}
if(l > e || r < s) return;
int mid = (l+r) / 2;
update(v*2,l,mid,s,e,val);
update(v*2+1,mid+1,r,s,e,val);
seg[v] = seg[v*2] + seg[v*2+1];
}
long double get(int v,int l,int r,int s)
{
check(v,l,r);
if(l == r) return seg[v];
int mid = (l+r) / 2;
if(s <= mid) return get(v*2,l,mid,s);
else return get(v*2+1,mid+1,r,s);
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
int c;
cin >> n;
cin >> c;
memset(ID,0,sizeof ID);
memset(mx,0,sizeof mx);
for(int i=0;i<=n+1;i++)g[i].clear();
memset(lazy,0,sizeof lazy);
for(int i = 1; i < n;++i)
{
int u , v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
bfs(1);
dfs(1,1);
update(1,1,n,ID[c],ID[c],1);
int m;
cin>>m;
long double ans=0;
cout<<fixed<<setprecision(10);
for(int i=0;i<m;i++)
{
int room;
cin>>room;
long double cur=get(1,1,n,ID[room]);
ans+=cur;
///update childs
update(1,1,n,min(mx[room],mx[room]-(int)g[room].size()+1+ (room != 1) ),mx[room],cur/g[room].size());
if(p[room]) update(1,1,n,ID[p[room]],ID[p[room]],cur/g[room].size());
///update room
update(1,1,n,ID[room],ID[room],-cur);
}
cout<<ans - 1<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
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...