Submission #91715

#	Time	Username	Problem	Language	Result	Execution time	Memory
91715		Mercenary	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	189 ms	24272 KiB

ballmachine

#include<bits/stdc++.h>

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
const int logn = log2(maxn) + 1;

int n , q , root;
vector<int> adj[maxn];
int P[maxn][logn];
int dp[maxn] , id[maxn] , id1[maxn];

void enter()
{
    cin >> n >> q;
    for(int i = 1 ; i <= n ; ++i)
    {
        int u;cin >> u;
        if(u == 0)root = i;
        else adj[u].pb(i) , P[i][0] = u;
    }
}

void DFS(int u)
{
    dp[u] = u;
    for(int c : adj[u])
        DFS(c) , dp[u] = min(dp[u] , dp[c]);
}

void Priority(int u)
{
    static int nTime = 0;
    sort(adj[u].begin(),adj[u].end(),[](const int x , const int y){
            return dp[x] < dp[y];
         });
    for(int c : adj[u])
        Priority(c);
    id[u] = ++nTime;id1[nTime] = u;
}

priority_queue<int,vector<int>,greater<int>> pq;
int vis[maxn];

void solve()
{
    for(int i = 1 ; i < logn ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            P[j][i] = P[P[j][i - 1]][i - 1];
    for(int i = 1 ; i <= n ; ++i)pq.push(i);
    while(q--)
    {
        int key;cin >> key;
        if(key == 1)
        {
            int k;cin >> k;
            int last;
            while(k--)
            {
                last = id1[pq.top()];
                vis[last] = 1;
                pq.pop();
            }
            cout << last << '\n';
        }
        else
        {
            int u;cin >> u;int res = 0;
            for(int i = logn - 1 ; i >= 0 ; --i)
                if(vis[P[u][i]])u = P[u][i] , res += (1 << i);
            pq.push(id[u]);vis[u] = 0;
            cout << res << '\n';
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    enter();
    DFS(root);Priority(root);solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:85:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
ballmachine.cpp:85:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:67:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << last << '\n';
                             ^~~~

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