oj.uz

답안 #971235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971235 2024-04-28T08:14:13 Z makanhulia Ball Machine (BOI13_ballmachine) C++17
65.7936 / 100
 1000 ms 15436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=1e5+5;
const ll INF=1e18;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, q, t, x, mn[maxn], par[maxn], root, dis[maxn], hrs, cnt, ans, nmr[maxn];
vi adj[maxn], arr;
bool use[maxn];
bool sub1=1;
priority_queue<pii, vector<pii>, greater<>> pq;
bool cmp(int a, int b) {
    return mn[a]<mn[b];
}
void dfs(int now) {
    mn[now]=now;
    for(auto it : adj[now]) {
        dis[it]=dis[now]+1;
        dfs(it);
        mn[now]=min(mn[now], mn[it]);
    }
}
void dfs2(int now) {
    if(!adj[now].empty()) {
        sort(adj[now].begin(), adj[now].end(), cmp);
        for(auto it : adj[now]) {
            dfs2(it);
        }
    }
    arr.pb(now);
}
int main() {
    ok
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> par[i];
        if(par[i]==0){
            root=i;
        } else adj[par[i]].pb(i);
    }
    dfs(root);
    for(int i=1; i<=n; i++) {
        if(!(adj[i].size()==2 || adj[i].empty())) sub1=0;
        if(adj[i].empty() && hrs && dis[i]!=hrs) sub1=0;
        if(adj[i].empty() && !hrs) hrs=dis[i];
    }
    dfs2(root);
    for(auto it : arr) {
        cnt++;
        nmr[it]=cnt;
        pq.push({cnt, it});
    }
    while(q--) {
        cin >> t >> x;
        if(t==1) {
            while(x--) {
                ans=pq.top().se;
                use[pq.top().se]=1;
                pq.pop();
            }
            cout << ans << endl;
        } else {
            ans=0;
            while(use[par[x]]) {
                ans++;
                x=par[x];
            }
            use[x]=0;
            pq.push({nmr[x], x});
            cout << ans << endl;
        }
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 43 ms 7160 KB Output is correct
3 Correct 30 ms 6992 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 10 ms 3928 KB Output is correct
11 Correct 41 ms 6992 KB Output is correct
12 Correct 29 ms 6992 KB Output is correct
13 Correct 42 ms 6988 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 5848 KB Output is correct
2 Correct 52 ms 12372 KB Output is correct
3 Correct 46 ms 8008 KB Output is correct
4 Correct 28 ms 6348 KB Output is correct
5 Correct 28 ms 6104 KB Output is correct
6 Correct 27 ms 6104 KB Output is correct
7 Correct 28 ms 5592 KB Output is correct
8 Correct 24 ms 5888 KB Output is correct
9 Correct 47 ms 12620 KB Output is correct
10 Correct 64 ms 12364 KB Output is correct
11 Correct 48 ms 12368 KB Output is correct
12 Correct 57 ms 10488 KB Output is correct
13 Correct 41 ms 15180 KB Output is correct
14 Correct 36 ms 8020 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 748 ms 8136 KB Output is correct
2 Execution timed out 1055 ms 10324 KB Time limit exceeded
3 Execution timed out 1054 ms 13664 KB Time limit exceeded
4 Execution timed out 1062 ms 10488 KB Time limit exceeded
5 Execution timed out 1036 ms 10116 KB Time limit exceeded
6 Execution timed out 1080 ms 10228 KB Time limit exceeded
7 Correct 809 ms 9080 KB Output is correct
8 Execution timed out 1046 ms 12888 KB Time limit exceeded
9 Execution timed out 1063 ms 11432 KB Time limit exceeded
10 Execution timed out 1083 ms 10868 KB Time limit exceeded
11 Execution timed out 1026 ms 10892 KB Time limit exceeded
12 Execution timed out 1059 ms 9312 KB Time limit exceeded
13 Execution timed out 1069 ms 15296 KB Time limit exceeded
14 Correct 45 ms 7248 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 11320 KB Time limit exceeded
2 Execution timed out 1077 ms 9300 KB Time limit exceeded
3 Correct 50 ms 15432 KB Output is correct
4 Execution timed out 1072 ms 11560 KB Time limit exceeded
5 Execution timed out 1048 ms 10844 KB Time limit exceeded
6 Correct 113 ms 11108 KB Output is correct
7 Execution timed out 1022 ms 9304 KB Time limit exceeded
8 Correct 66 ms 15436 KB Output is correct
9 Correct 36 ms 7256 KB Output is correct