oj.uz

답안 #726948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
726948 2023-04-19T16:29:00 Z TB_ Ball Machine (BOI13_ballmachine) C++17
100 / 100
 276 ms 40196 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<(int)n;i++)
#define Fo(i, k, n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define sp(x, y) fixed<<setprecision(y)<<x
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define trr(it, x) for(auto it = x.rbegin(); it != x.rend(); it+)
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

vvpii adj(100001);
vi amount(100001, 0);
vpii rem(100001);
set<pii> ordered;

int dfsSort(int u, int last){
    int best = u;
    vl vals;
    for(auto v : adj[u]){
        vals.pb(INF);
        if(last == v.S) continue;
        int val = dfsSort(v.S, u);
        best = min(best, val);
        vals[vals.size()-1] = val;
    }
    fo(i, adj[u].size())adj[u][i].F = vals[i];
    sort(all(adj[u]));
    return best;
}

void dfsUn(int u, int last){
    // deb(v.F);
    for(auto v : adj[u]){
        if(last == v.S) continue;
        dfsUn(v.S, u);
    }
    rem[u] = {ordered.size(), u};
    ordered.insert({ordered.size(), u});
}

int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit); // remove if to endof file

    int n, q, to, typ;
    cin >> n >> q;
    int root = -1;
    vvi bl(n, vi(30, -1));
    fo(i, n){
        cin >> to;
        bl[i][0] = to-1;
        if(!to) {
            adj[i].pb({INF, i});
            root = i;
            bl[i][0] = i;
        }
        else adj[to-1].pb({0, i});
    }
    dfsSort(root, root);
    dfsUn(root, root);

    fo(i, 25){
        fo(j, n){
            bl[j][i+1] = bl[bl[j][i]][i];
        }
    }

    fo(i, q){
        cin >> typ >> to;
        if(typ == 1){
            // cout << dfs(root, to)+1 << "\n";
            int ans = -1;
            vpii re;
            for(auto v : ordered){
                to--;
                re.pb(v);
                amount[v.S] = 1;
                ans = v.S;
                if(!to) break;
            }
            fo(j, re.size()) ordered.erase(re[j]);
            cout << ans+1 << "\n";
        }else{
            int current = to-1;
            int ans = 0;
            bool isRoot = false;
            for(int bit = 23; bit>=0; bit--){
                // deb(bl[current][bit]);
                if(amount[bl[current][bit]]) {
                    if(bl[current][bit] == root) {
                        isRoot = true;
                        continue;
                    }
                    current = bl[current][bit];
                    ans += (1<<bit);
                }
            }
            // deb(current);
            if(isRoot) current = bl[current][0];
            amount[current] = 0;
            ordered.insert(rem[current]);
            cout << ans+isRoot << "\n";
        }
        // fo(j, n) deb(amount[j]);
    }


    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 138 ms 18484 KB Output is correct
3 Correct 86 ms 18100 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 3 ms 4052 KB Output is correct
8 Correct 3 ms 4052 KB Output is correct
9 Correct 10 ms 4692 KB Output is correct
10 Correct 34 ms 7468 KB Output is correct
11 Correct 155 ms 18596 KB Output is correct
12 Correct 86 ms 17996 KB Output is correct
13 Correct 115 ms 17892 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 10444 KB Output is correct
2 Correct 216 ms 32888 KB Output is correct
3 Correct 114 ms 25072 KB Output is correct
4 Correct 77 ms 12940 KB Output is correct
5 Correct 80 ms 12688 KB Output is correct
6 Correct 67 ms 12348 KB Output is correct
7 Correct 88 ms 11108 KB Output is correct
8 Correct 39 ms 10444 KB Output is correct
9 Correct 243 ms 33140 KB Output is correct
10 Correct 276 ms 32896 KB Output is correct
11 Correct 223 ms 31964 KB Output is correct
12 Correct 234 ms 29084 KB Output is correct
13 Correct 150 ms 35248 KB Output is correct
14 Correct 116 ms 25100 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 18636 KB Output is correct
2 Correct 253 ms 29724 KB Output is correct
3 Correct 159 ms 32572 KB Output is correct
4 Correct 147 ms 27240 KB Output is correct
5 Correct 160 ms 26756 KB Output is correct
6 Correct 214 ms 26828 KB Output is correct
7 Correct 148 ms 24300 KB Output is correct
8 Correct 161 ms 32588 KB Output is correct
9 Correct 249 ms 33228 KB Output is correct
10 Correct 234 ms 32944 KB Output is correct
11 Correct 240 ms 32964 KB Output is correct
12 Correct 237 ms 29756 KB Output is correct
13 Correct 256 ms 40196 KB Output is correct
14 Correct 188 ms 26540 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 33484 KB Output is correct
2 Correct 241 ms 29728 KB Output is correct
3 Correct 162 ms 39372 KB Output is correct
4 Correct 248 ms 33584 KB Output is correct
5 Correct 239 ms 32952 KB Output is correct
6 Correct 172 ms 32116 KB Output is correct
7 Correct 271 ms 29800 KB Output is correct
8 Correct 146 ms 39428 KB Output is correct
9 Correct 126 ms 25192 KB Output is correct