Submission #527511

#	Time	Username	Problem	Language	Result	Execution time	Memory
527511		Kipras	Tax Evasion (LMIO19_mokesciai)	C++17	100 / 100	443 ms	55652 KiB

mokesciai

#include <bits/stdc++.h>

using namespace std;

const int maxN = 2e5+10;
const int maxLog = 32;

int n, m;
vector<int> adj[maxN];
int dep[maxN]={0};
int par[maxN][maxLog]={0};
int best[maxN];

void dfs(int v, int u){
    dep[v]=dep[u]+1;
    par[v][0]=u;
    for(auto i : adj[v]){
        if(i==u)continue;
        dfs(i, v);
    }
}

int lift(int p, int x){
    for(int i = 0; i < maxLog; i++){
        if(x&(1<<i)){
            p=par[p][i];
        }
    }
    return p;
}
bool isPossible;

int possible(int v, int u, int val){
    int counter=0;
    for(auto i : adj[v]){
        if(i==u)continue;
        counter+=possible(i, v, val);
    }
    if(dep[v]>=val-1)counter++;
    if(counter<best[v]){isPossible=false;/*cout<<v<<" "<<val<<" "<<best[v]<<" "<<counter<<"bbb"<<endl;*/};
    counter-=best[v];
    return counter;
}

int solve(){
    int l=0, h=n;
    while(l<h-1){
        int mid = l+(h-l)/2;
        //cout<<mid<<" "<<l<<" "<<h<<endl;
        isPossible=true;
        possible(1, 0, mid);
        if(isPossible)l=mid;
        else h=mid-1;
    }
    isPossible=true;
    possible(1, 0, h+1);
    if(isPossible)return h+1;
    isPossible=true;
    possible(1, 0, h);
    if(isPossible)return h;
    isPossible=true;
    possible(1, 0, h-1);
    if(isPossible)return h-1;
}

int main()
{

    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    cin>>n>>m;
    for(int i = 2; i <= n; i++){
        int aa;
        cin>>aa;
        adj[aa].push_back(i);
        adj[i].push_back(aa);
    }

    dep[0]=-1;
    par[0][0]=0;
    dfs(1, 0);

    for(int i = 1; i < maxLog; i++)for(int x = 1; x <= n; x++)par[x][i]=par[par[x][i-1]][i-1];

    for(int i = 1; i <= m; i++){
        int aa;
        cin>>aa;
        //cout<<lift(aa, (dep[i]-1)/2)<<" "<<(dep[i]-1)/2<<endl;
        best[lift(aa, (dep[aa]-1)/2)]++;
    }//cout<<endl;

    cout<<solve();

    return 0;
}

Compilation message (stderr)

mokesciai.cpp: In function 'int solve()':
mokesciai.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
   64 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29