Submission #535393

#	Time	Username	Problem	Language	Result	Execution time	Memory
535393		Karabasan	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	149 ms	46992 KiB

ballmachine

#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define int long long
#define mod 1000000007
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,avx")
#pragma GCC optimize("unroll-loops")

int n,q;
int par[100005];
vector<int> v[100005];
int root;
vector<int> dizi;
int sub[100005];
vector<pair<int,int> > sira[100005];
int mark=0;
int boya[100005];
int yer[100005];
int ata[100005][25];
int dfs(int x,int y)
{
    sub[x]=x;
    if(v[x].size()==1&&x!=root)
        return sub[x]=x;
    for(auto i:v[x])
    {
        if(i==y)
            continue;
        sira[x].push_back({dfs(i,x),i});
    }
    sort(sira[x].begin(),sira[x].end());
    for(int i=0;i<sira[x].size();i++)
        sub[x]=min(sub[x],sira[x][i].first);
    return sub[x];
}
void dps(int x)
{
    for(int i=0;i<sira[x].size();i++)
        dps(sira[x][i].second);
    dizi.push_back(x);
    yer[x]=dizi.size()-1;
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>ata[i][0];
        if(ata[i][0]==0)
        {
            root=i;
            continue;
        }
        v[i].push_back(ata[i][0]);
        v[ata[i][0]].push_back(i);
    }
    dfs(root,0);
    dps(root);
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            ata[j][i]=ata[ata[j][i-1]][i-1];
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        if(a==1)
        {
            int c=0;
            int ind=0;
            while(c<b)
            {
                if(boya[dizi[ind]]==0)
                    c++;
                boya[dizi[ind]]=1;
                ind++;
            }
            cout<<dizi[ind-1]<<endl;
        }
        else
        {
            int cvp=0;
            for(int i=20;i>=0;i--)
            {
                if(boya[ata[b][i]]==1)
                {
                    b=ata[b][i];
                    cvp+=(1<<i);
                }
            }
            boya[b]=0;
            cout<<cvp<<endl;
        }
    }
}
signed main()
{
    fast1
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'long long int dfs(long long int, long long int)':
ballmachine.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<sira[x].size();i++)
      |                 ~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dps(long long int)':
ballmachine.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<sira[x].size();i++)
      |                 ~^~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5