oj.uz

Submission #370313

# Submission time Handle Problem Language Result Execution time Memory
370313 2021-02-23T17:38:02 Z ACmachine Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 1000 ms 32980 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> order;
    vector<vector<int>> nxt(n, vector<int>(20, -1));
    function<void(int, int)> dfs = [&](int v, int p){
        sort(all(g[v]));
        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:123:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  123 |             cout << res + 1 << "\n";
      |                                ^~~~
ballmachine.cpp:62:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |     int root;
      |         ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Execution timed out 1092 ms 16496 KB Time limit exceeded
3 Incorrect 96 ms 16644 KB Output isn't correct
4 Execution timed out 1087 ms 364 KB Time limit exceeded
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 2 ms 620 KB Output isn't correct
7 Execution timed out 1095 ms 620 KB Time limit exceeded
8 Execution timed out 1091 ms 620 KB Time limit exceeded
9 Incorrect 7 ms 1388 KB Output isn't correct
10 Execution timed out 1098 ms 4332 KB Time limit exceeded
11 Incorrect 154 ms 16752 KB Output isn't correct
12 Incorrect 95 ms 16624 KB Output isn't correct
13 Incorrect 120 ms 16624 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6764 KB Output is correct
2 Incorrect 277 ms 28856 KB Output isn't correct
3 Incorrect 116 ms 24680 KB Output isn't correct
4 Execution timed out 1094 ms 9068 KB Time limit exceeded
5 Execution timed out 1099 ms 8684 KB Time limit exceeded
6 Incorrect 78 ms 9324 KB Output isn't correct
7 Incorrect 86 ms 8172 KB Output isn't correct
8 Correct 44 ms 6764 KB Output is correct
9 Incorrect 214 ms 28776 KB Output isn't correct
10 Incorrect 276 ms 28908 KB Output isn't correct
11 Incorrect 222 ms 28648 KB Output isn't correct
12 Incorrect 242 ms 26084 KB Output isn't correct
13 Correct 200 ms 28900 KB Output is correct
14 Incorrect 116 ms 24552 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 14568 KB Output isn't correct
2 Incorrect 289 ms 26784 KB Output isn't correct
3 Correct 217 ms 26084 KB Output is correct
4 Incorrect 170 ms 22888 KB Output isn't correct
5 Incorrect 197 ms 22888 KB Output isn't correct
6 Incorrect 193 ms 22756 KB Output isn't correct
7 Incorrect 180 ms 21224 KB Output isn't correct
8 Correct 224 ms 26020 KB Output is correct
9 Incorrect 272 ms 28904 KB Output isn't correct
10 Incorrect 300 ms 28648 KB Output isn't correct
11 Incorrect 301 ms 28648 KB Output isn't correct
12 Incorrect 286 ms 26856 KB Output isn't correct
13 Correct 324 ms 32980 KB Output is correct
14 Incorrect 190 ms 24808 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 28776 KB Output isn't correct
2 Incorrect 276 ms 26984 KB Output isn't correct
3 Correct 230 ms 32484 KB Output is correct
4 Incorrect 245 ms 28776 KB Output isn't correct
5 Incorrect 276 ms 28648 KB Output isn't correct
6 Incorrect 232 ms 28648 KB Output isn't correct
7 Incorrect 266 ms 26728 KB Output isn't correct
8 Correct 225 ms 32612 KB Output is correct
9 Incorrect 124 ms 24552 KB Output isn't correct