Submission #1231303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231303		Malix	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	86 ms	201792 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vii a;
int dist[200000],vis[100000];
vi st,lazy,lazyval,p,arr,s,b;

void dfs(int x){
    arr.PB(x);
    vis[x]=1;
    for(auto u:a[x])if(!vis[u]){
        dist[u]=dist[x]+1;
        dfs(u);
        s[x]+=s[u];
    }
}

void propagate(int x){
    if(!lazy[x])return;
    lazy[x]=0;
    st[2*x]=min(st[2*x],lazyval[x]);
    st[2*x+1]=min(st[2*x+1],lazyval[x]);
    lazy[2*x]=1;
    lazy[2*x+1]=1;
    lazyval[2*x]=lazyval[x];
    lazyval[2*x+1]=lazyval[x];
}

int query(int x,int l,int r,int u){
    if(l==r)return st[x];
    propagate(x);
    int m=(l+r)/2;
    if(u<=m)return query(2*x,l,m,u);
    else return query(2*x+1,m+1,r,u);
}

void update(int x,int l,int r,int u,int v,int y){
    if(u>v)return;
    if(l!=r)propagate(x);
    if(u==l&&v==r){
        st[x]=min(st[x],y);
        lazy[x]=1;
        lazyval[x]=y;
        return;
    }
    int m=(l+r)/2;
    update(2*x,l,m,u,min(m,v),y);
    update(2*x+1,m+1,r,max(u,m+1),v,y);
    st[x]=min(st[2*x],st[2*x+1]);
}

int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
freopen("test_input.txt", "r", stdin);
freopen("test_output.txt", "w", stdout);
    int n,d;cin>>n>>d;
    a.resize(n);p.resize(n,-1);
    REP(i,1,n){
        int x;cin>>x;
        p[i]=x;
        a[x].PB(i);
        a[i].PB(x);
    }
    st.resize(4*n+1,inf);
    lazy.resize(4*n+1,0);
    lazyval.resize(4*n+1,0);
    s.resize(n,1);
    memset(vis,0,sizeof(vis));
    dist[0]=0;
    dfs(0);
    b.resize(n);
    REP(i,0,n)b[arr[i]]=i;
    priority_queue<pi> pq;
    REP(i,0,n)pq.push({dist[i],i});
    int ans=0;
    while(!pq.empty()){
        int x=pq.top().S;
        pq.pop();
        if(query(1,0,n-1,b[x])+dist[x]<d)continue;
        ans++;
        int t=d,z=x;
        while(t--&&x!=-1){
            int y=b[x];
            update(1,0,n-1,y,y+s[x]-1,dist[z]-2*dist[x]);
            x=p[x];
        }
    }
    cout<<ans;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:75:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 | freopen("test_input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:76:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 | freopen("test_output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49