QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#65206#4433. Kitten and RoombaAmrMohameDTL 0ms0kbC++3.7kb2022-11-28 02:04:582022-11-28 02:05:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-28 02:05:02]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-11-28 02:04:58]
  • 提交

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

詳細信息

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

output:


result: