Submission #225229

#	Time	Username	Problem	Language	Result	Execution time	Memory
225229		MKopchev	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	472 ms	156908 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e6+42;
long long n,d;
vector< pair<int/*to*/,int/*dist*/> > adj[nmax];

long long depth[nmax];

vector<int> output;

int up[20][nmax];

int level[nmax];

int in[nmax],out[nmax];

int seen[nmax],t=0;

pair<int/*min level*/,int/*node*/> table[20][nmax];

void dfs(int node,int par)
{
    up[0][node]=par;

    level[node]=level[par]+1;

    t++;
    in[node]=t;

    seen[t]=node;

    for(auto k:adj[node])
        if(k.first!=par)
        {
            depth[k.first]=depth[node]+k.second;
            dfs(k.first,node);

            t++;
            seen[t]=node;
        }

    t++;
    seen[t]=node;

    out[node]=t;
}

int inv[nmax];

int query(int l,int r)
{
    int k=inv[r-l+1];

    return min(table[k][l],table[k][r-(1<<k)+1]).second;
}
int lca(int u,int v)
{
    return query(min(in[u],in[v]),max(out[u],out[v]));
}
long long tree_dist(int u,int v)
{
    return depth[u]+depth[v]-2*depth[lca(u,v)];
}

bool been[nmax];

int parent_centroid[nmax];

long long nearest[nmax];

int SZ[nmax];

void dfs_sz(int node,int par)
{
    SZ[node]=1;
    for(auto k:adj[node])
        if(k.first!=par&&been[k.first]==0)
        {
            dfs_sz(k.first,node);
            SZ[node]+=SZ[k.first];
        }
}
int centroid(int node)
{
    dfs_sz(node,0);

    int low=SZ[node]/2;

    while(1)
    {
        bool stop=1;
        for(auto k:adj[node])
            if(SZ[node]>SZ[k.first]&&SZ[k.first]>low)
            {
                node=k.first;
                stop=0;
                break;
            }
        if(stop)break;
    }

    return node;
}
int decomp(int node)
{
    node=centroid(node);

    been[node]=1;

    for(auto k:adj[node])
        if(been[k.first]==0)
        {
            parent_centroid[decomp(k.first)]=node;
        }

    return node;
}

priority_queue< pair<long long,int> > pq;

long long closest(int node)
{
    long long ret=1e18;
    int help=node;
    while(help)
    {
        ret=min(ret,tree_dist(node,help)+nearest[help]);
        help=parent_centroid[help];
    }
    return ret;
}

int go_up(int node)
{
    int help=node;
    for(int i=19;i>=0;i--)
        if(depth[node]-depth[up[i][help]]<=d)help=up[i][help];
    return help;
}

void update(int node)
{
    int help=node;
    while(help)
    {
        nearest[help]=min(nearest[help],tree_dist(help,node));
        help=parent_centroid[help];
    }
}
int main()
{
    scanf("%lld%lld",&n,&d);

    int u,v,dist;
    for(int i=1;i<n;i++)
    {
        scanf("%i",&v);
        u=i+1;
        v++;

        //cout<<u<<" "<<v<<endl;

        adj[u].push_back({v,1});
        adj[v].push_back({u,1});
    }

    dfs(1,1);

    for(int i=1;i<=t;i++)
        table[0][i]={level[seen[i]],seen[i]};

    for(int st=1;st<20;st++)
        for(int i=1;i+(1<<st)-1<=t;i++)
            table[st][i]=min(table[st-1][i],table[st-1][i+(1<<(st-1))]);

    for(int i=1;i<=t;i++)
    {
        while(2*(1<<inv[i])<i)inv[i]++;
    }

    for(int st=1;st<20;st++)
        for(int i=1;i<=n;i++)
            up[st][i]=up[st-1][up[st-1][i]];

    decomp(1);
    /*
    for(int i=1;i<=t;i++)
    {
        cout<<seen[i]<<" ";
    }
    cout<<endl;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<lca(i,j)<<" ";
        }
        cout<<endl;
    }


    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<tree_dist(i,j)<<" ";
        }
        cout<<endl;
    }

    cout<<"t= "<<t<<endl;

    for(int i=1;i<=n;i++)cout<<i<<" -> "<<parent_centroid[i]<<endl;
    */

    for(int i=1;i<=n;i++)nearest[i]=1e18;

    for(int i=1;i<=n;i++)pq.push({depth[i],i});

    while(pq.size())
    {
        pair<long long,int> tp=pq.top();
        pq.pop();
        /*
        cout<<"---"<<endl;

        for(int i=1;i<=n;i++)
            cout<<i<<" -> "<<closest(i)<<endl;
        */

        if(closest(tp.second)<d)continue;

        int actual=tp.second;

        output.push_back(actual);

        update(actual);
        /*
        cout<<"update "<<actual<<endl;

        cout<<"nearest: "<<endl;
        for(int i=1;i<=n;i++)
            cout<<i<<" -> "<<nearest[i]<<endl;
        cout<<"---"<<endl;
        */
    }

    sort(output.begin(),output.end());

    printf("%i\n",output.size());
    /*
    for(int i=0;i<output.size();i++)
    {
        printf("%i",output[i]);
        if(i==output.size()-1)printf("\n");
        else printf(" ");
    }
    */
    return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:251:32: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%i\n",output.size());
                   ~~~~~~~~~~~~~^
catinatree.cpp:154:13: warning: unused variable 'dist' [-Wunused-variable]
     int u,v,dist;
             ^~~~
catinatree.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&d);
     ~~~~~^~~~~~~~~~~~~~~~~~
catinatree.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&v);
         ~~~~~^~~~~~~~~

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