oj.uz

답안 #370314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370314 2021-02-23T17:47:51 Z ACmachine Ball Machine (BOI13_ballmachine) C++17
100 / 100
 373 ms 33380 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
  
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
    int n, q;
    cin >> n >> q;
    int root;
    vector<vector<int>> g(n);
    REP(i, n){
        int p; cin >> p;
        p--;
        if(p == -1)
            root = i;
        else{
            g[i].pb(p);
            g[p].pb(i);
        }
    }
    vector<int> subtree_minimum(n, INF);
    REP(i, n) subtree_minimum[i] = i;
    function<void(int, int)> gmin = [&](int v, int p){
        for(int x : g[v]){
            if(x == p) continue;
            gmin(x, v);
            subtree_minimum[v] = min(subtree_minimum[v], subtree_minimum[x]);
        }
    };
    gmin(root, -1);
    vector<int> order;
    vector<vector<int>> nxt(n, vector<int>(20, -1));
    function<void(int, int)> dfs = [&](int v, int p){
        auto cmp = [&](int lhs, int rhs){
            return subtree_minimum[lhs] < subtree_minimum[rhs];
        };
        sort(all(g[v]), cmp);
        nxt[v][0] = p; 
        FOR(i, 1, 20, 1){
            if(nxt[v][i - 1] != -1){
                nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
            }
        } 
        for(int x : g[v]){
            if(x == p) continue;
            dfs(x, v);
        }
        order.pb(v);
    };
    dfs(root, -1);
    vector<int> pos(n);
    REP(i, n) pos[order[i]] = i;
    set<int> free_positions;
    REP(i, n) free_positions.insert(i);
    vector<bool> isfree(n, true);
    auto insert_ball = [&](){
        int pos = *free_positions.begin();
        isfree[order[pos]] = false;
        free_positions.erase(free_positions.begin());
        return order[pos];
    };
    auto erase_ball = [&](int v){
        int x = v;
        int res = 0;
        REPD(i, 19){
            if(nxt[x][i] != -1 && !isfree[nxt[x][i]]){
                x = nxt[x][i];
                res += (1 << i);
            }
        }
        isfree[x] = true;
        free_positions.insert(pos[x]);
        return res;
    };
    REP(i, q){
        int type; cin >> type;
        if(type == 1){
            int k; cin >> k;
            int res;
            REP(j, k){
                res = insert_ball(); 
            }
            cout << res + 1 << "\n";
        }
        else{
            int x; cin >> x;
            x--;
            int res = erase_ball(x);
            cout << res << "\n";
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:136:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |             cout << res + 1 << "\n";
      |                                ^~~~
ballmachine.cpp:62:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |     int root;
      |         ^~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 151 ms 15752 KB Output is correct
3 Correct 100 ms 15984 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 10 ms 1260 KB Output is correct
10 Correct 25 ms 4204 KB Output is correct
11 Correct 153 ms 15728 KB Output is correct
12 Correct 100 ms 15856 KB Output is correct
13 Correct 130 ms 15728 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 6508 KB Output is correct
2 Correct 297 ms 28524 KB Output is correct
3 Correct 132 ms 23784 KB Output is correct
4 Correct 100 ms 9068 KB Output is correct
5 Correct 93 ms 9196 KB Output is correct
6 Correct 77 ms 8812 KB Output is correct
7 Correct 82 ms 7532 KB Output is correct
8 Correct 45 ms 6508 KB Output is correct
9 Correct 226 ms 28392 KB Output is correct
10 Correct 272 ms 28396 KB Output is correct
11 Correct 248 ms 28520 KB Output is correct
12 Correct 252 ms 25572 KB Output is correct
13 Correct 219 ms 29540 KB Output is correct
14 Correct 129 ms 23888 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 14440 KB Output is correct
2 Correct 313 ms 26136 KB Output is correct
3 Correct 240 ms 26724 KB Output is correct
4 Correct 194 ms 23016 KB Output is correct
5 Correct 204 ms 22760 KB Output is correct
6 Correct 205 ms 22884 KB Output is correct
7 Correct 211 ms 20968 KB Output is correct
8 Correct 236 ms 26724 KB Output is correct
9 Correct 302 ms 28520 KB Output is correct
10 Correct 332 ms 28648 KB Output is correct
11 Correct 341 ms 28520 KB Output is correct
12 Correct 327 ms 26320 KB Output is correct
13 Correct 373 ms 33380 KB Output is correct
14 Correct 213 ms 23912 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 28648 KB Output is correct
2 Correct 323 ms 26248 KB Output is correct
3 Correct 268 ms 33252 KB Output is correct
4 Correct 289 ms 28800 KB Output is correct
5 Correct 318 ms 28612 KB Output is correct
6 Correct 269 ms 28536 KB Output is correct
7 Correct 316 ms 26320 KB Output is correct
8 Correct 259 ms 33252 KB Output is correct
9 Correct 128 ms 23912 KB Output is correct