Submission #1202819


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

#define BITTYPE int
#define BITCNT  1
#define BITSIZE 512345
namespace BIT_{
    int i=0;
    BITTYPE t[BITCNT][BITSIZE];
    inline BITTYPE* get(){
        i%=BITCNT;
        return t[i++];
    }
}
//[1,n],0は扱えない!
struct BIT{
    using T=BITTYPE;
    T* bit;
    int n;
    BIT(T* _table,int n):bit(_table),n(n){
        std::fill(bit,bit+n+1,0);
    }
    BIT(int n):BIT(BIT_::get(),n){}
    T sum(int i){
        T s=0;
        while(i>0){
            s+=bit[i];
            i-=i&-i;
        }
        return s;
    }
    T sum(int lb,int ub){
        return sum(ub)-sum(lb-1);
    }
    void add(int i,T x){
        while(i<=n){
            bit[i]+=x;i+=i&-i;
        }
    }
    //v[1]+v[2]+...+v[x]>=wとなる最小のxを求める
    int lowerbound(T w){
        if(w<=0)return 0;
        int x=0;
        for(int k = (1<<(31-__builtin_clz(n)));k >0 ;k>>=1)
            if(x+k<=n&&bit[x+k]<w){
                w-=bit[x+k];
                x+=k;
            }
        return x+1;
    }
    void clear(int sz){
        std::fill(bit,bit+n+1,0);
    }

};   
typedef vector<int> V;
typedef vector<V> VV;
map<LL,int> z;
int N,Q;

int a[112345];
int b[112345];
LL  l[112345];
LL depth[112345];
LL  leaf[112345];
LL query[112345];
int res[312345];
VV g;
int sync(){
    int cnt=1;
    for(auto &it:z)it.second=cnt++;
    REP(i,N)depth[i]=z[depth[i]];
    REP(i,N)leaf[i]=z[leaf[i]];
    REP(i,Q)query[i]=z[query[i]];
    REP(i,cnt+1)res[i]=1145141919;
    return cnt;
}

void latte(int v,int p,LL d){
    z[d]=0;
    leaf[v]=d;
    depth[v]=d;
    for(auto &e:g[v]){
        int u=v^a[e]^b[e];
        LL nd=d+l[e];
        if(u==p)continue;
        latte(u,v,nd);
        chmax(leaf[v],leaf[u]);
    }
}
void malta(int v,int p,BIT &bit){
    for(auto &e:g[v]){
        int u=v^a[e]^b[e];
        if(u==p)continue;
        bit.add(leaf[u],1);
    }
    int cost=bit.sum(depth[v]+1,z.size());
    chmin(res[depth[v]],cost);
    for(auto &e:g[v]){
        int u=v^a[e]^b[e];
        if(u==p)continue;
        bit.add(leaf[u],-1);
        malta(u,v,bit);
        bit.add(leaf[u],1);

    }
    for(auto &e:g[v]){
        int u=v^a[e]^b[e];
        if(u==p)continue;
        bit.add(leaf[u],-1);
    }    

}

int main(){
    LL K;
    cin>>N>>K;
    g.resize(N);
    REP(i,N-1)cin>>l[i];
    REP(i,N-1){
        a[i]=i+1;
        cin>>b[i];
        b[i]--;
        g[a[i]].pb(i);
        g[b[i]].pb(i);
    }
    cin>>Q;
    REP(i,Q){
        cin>>query[i];
        z[query[i]]=0;
    }
    latte(0,0,K);
    int sz=sync();
    BIT bit(sz+10);
    malta(0,0,bit);
    REP(i,Q){
        int ret=res[query[i]];
        if(ret==1145141919)ret=-1;
        cout<<ret<<fin;
    }
    return 0;
}

Submission Info

Submission Time
Task I - 風船ツリー
User btk15049
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3590 Byte
Status AC
Exec Time 217 ms
Memory 28416 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 35
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 217 ms 21376 KB
01-02.txt AC 2 ms 4352 KB
01-03.txt AC 2 ms 4352 KB
01-04.txt AC 177 ms 14464 KB
01-05.txt AC 173 ms 14336 KB
01-06.txt AC 185 ms 14464 KB
01-07.txt AC 173 ms 14208 KB
01-08.txt AC 183 ms 14464 KB
01-09.txt AC 122 ms 13440 KB
01-10.txt AC 42 ms 11384 KB
01-11.txt AC 112 ms 12280 KB
01-12.txt AC 112 ms 12280 KB
01-13.txt AC 140 ms 28416 KB
01-14.txt AC 138 ms 28416 KB
01-15.txt AC 138 ms 28416 KB
01-16.txt AC 146 ms 20480 KB
01-17.txt AC 149 ms 20480 KB
01-18.txt AC 169 ms 22912 KB
01-19.txt AC 53 ms 10880 KB
01-20.txt AC 46 ms 11264 KB
01-21.txt AC 42 ms 11392 KB
01-22.txt AC 42 ms 11264 KB
01-23.txt AC 40 ms 11264 KB
01-24.txt AC 164 ms 13824 KB
01-25.txt AC 130 ms 13184 KB
01-26.txt AC 127 ms 13440 KB
01-27.txt AC 117 ms 12672 KB
01-28.txt AC 124 ms 12800 KB
01-29.txt AC 200 ms 15232 KB
01-30.txt AC 180 ms 14976 KB
01-31.txt AC 188 ms 15104 KB
sample-01.txt AC 2 ms 4352 KB
sample-02.txt AC 2 ms 4352 KB