제출 #1290196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290196		harut_13	Ball Machine (BOI13_ballmachine)	C++20	79.76 / 100	1098 ms	46092 KiB

ballmachine

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>


#define FASTIO ios_base::sync_with_stdio(0);cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define endl '\n'
#define ll   long long
#define ull unsigned long long
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define MOD 100000007
#define MODD 998244353
#define pi 3.141592653589793238463
#define INF 1000000000000000000


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return res * res * a;
    }
    else {
        return res * res;
    }
}
int n, armat;
vector<vec> gp;
vec order, sub, par;
vector<vec> up;
int L;
set<pll> ka, chka;
vec dist;
void sort_dfs(int u, int p) {
    vector<pii> cur;
    if (u != armat)cur.pshb({ 1e6,p });
    up[u][0] = p;
    for (int i = 1; i < L; i++)up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto& x : gp[u]) {
        if (x != p) {
            dist[x] = dist[u] + 1;
            sort_dfs(x, u);
            sub[u] = min(sub[u], sub[x]);
            cur.pshb({ sub[x],x });
        }
    }
    sort(cur.begin(), cur.end());
    for (int i = 0; i < cur.sz; i++)gp[u][i] = cur[i].ss;
}
void order_dfs(int u, int p) {
    for (auto& x : gp[u]) {
        if (x != p)order_dfs(x, u);
    }
    order.pshb(u);
}
void solve() {
    cin >> n;
    int m; cin >> m;
    gp = vector<vec>(n);
    par = vec(n);
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        a--;
        if (a == -1)armat = i;
        else {
            gp[i].pshb(a);
            gp[a].pshb(i);
        }
        par[i] = a;
    }
    vector<pii> harc(m);for (int i = 0; i < m; i++)cin >> harc[i].ff >> harc[i].ss;
    L = ceil(log2(n)) + 1;
    up = vector<vec>(n, vec(L));
    sub = vec(n); for (int i = 0; i < n; i++)sub[i] = i;
    dist = vec(n);
    sort_dfs(armat, armat);
    order_dfs(armat, armat);
    /*for (int i = 0; i < n; i++) {
        cout << "??" << i + 1 << "...";
        for (int j = 0; j < gp[i].sz; j++) {
            cout << gp[i][j] +1<< " ";
        }
        cout << endl;
    }
     for (int i : order)cout << i + 1 <<" ";
     
    return;*/
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        mp[order[i]] = i;
        chka.insert({ i,order[i] });
    }
    for (int i = 0; i < m; i++) {
       //cin >> harc[i].ff >> harc[i].ss;
        if (harc[i].ff == 1) {
            vector<pii> noric;
            int k = harc[i].ss;
            for (auto x : chka) {
                noric.pshb(x);
                k--;
                if (!k)break;
            }
            for (auto x : noric) {
                chka.erase(x);
                ka.insert(x);
            }
            cout << noric.back().ss + 1 << endl;
        }
        else {
            int gag = harc[i].ss - 1;
            ll ans = 0;
            for (int elni = L-1; elni >= 0; elni--) {
                //cout << "??" << gag << endl;
                int gag_elni = up[gag][elni];
                if (ka.find({ mp[gag_elni],gag_elni }) != ka.end()) {
                    gag = gag_elni;
                }
            }
            ka.erase({ mp[gag],gag });
            chka.insert({ mp[gag],gag });
            cout << dist[harc[i].ss - 1] - dist[gag] << endl;
        }
        //cout << "??" << i << endl;
    }
}



signed main() {
    FASTIO
        //        freopen("tracing.in", "r", stdin);
   //     int t; cin >> t;
   // while (t--)
        solve();
}

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