oj.uz

답안 #859212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859212 2023-10-10T01:36:11 Z 8pete8 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 43208 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<list>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
//#define p push
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=69,lg=30,root=80,inf=1e18;
vector<ppii>adj[mxn+10];
int up[mxn+10][lg+5],h[mxn+10],st,go[mxn+10];
bitset<mxn+10>on;
int dfs(int cur,int p){
    int cm=inf;
    for(auto &i:adj[cur]){
        h[i.f]=h[cur]+1;
        int k=dfs(i.f,cur);
        cm=min(cm,k);
        i.s.f=k;
    }
    return min(cm,cur);
}
int solve(int cur,int p){
    int cm=inf;
    for(auto &i:adj[cur])cm=min(cm,i.s.f);
    for(auto &i:adj[cur]){
        i.s.s=solve(i.f,cur);
        if(i.s.f==cm)go[cur]=i.s.s;
    }
    if(cm==inf)return cur;
    return go[cur];
}
int32_t main(){
    fastio
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        if(a==0){
            st=i;
            continue;
        }
        adj[a].pb({i,{-1,-1}});
        up[i][0]=a;
    }
    priority_queue<pii>pq;
    dfs(st,-1);
    solve(st,-1);
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    while(m--){
        int t;cin>>t;
        if(t==1){
            int k;cin>>k; 
            int ans=0;
            for(int j=0;j<k;j++){
                while(!pq.empty()&&!on[pq.top().s])pq.pop();
                while(!pq.empty()&&on[up[pq.top().s][0]])pq.pop();
                if(pq.empty())pq.push({h[go[st]],go[st]}),on[go[st]]=true,ans=go[st];
                else{
                    int cur=pq.top().s;
                    cur=up[cur][0];
                    int cm=inf;
                    pq.pop();
                    for(auto i:adj[cur])if(!on[i.f])cm=min(cm,i.s.f);
                    for(auto i:adj[cur])if(i.s.f==cm)pq.push({h[i.s.s],i.s.s}),on[i.s.s]=true,ans=i.s.s;
                    if(cm==inf){
                        on[cur]=true;
                        ans=cur;
                        pq.push({h[cur],cur});
                    }
                }
            }
            cout<<ans<<'\n';
        }
        else{
            int x,y,diff;cin>>x;
            y=x;
            for(int i=lg;i>=0;i--)if(on[up[x][i]])x=up[x][i];
            diff=h[y]-(h[x]+1);
            for(int i=0;i<=lg;i++)if(diff&(1<<i))y=up[y][i];
            on[x]=false;
            on[y]=true;
            pq.push({h[y],y});
            cout<<diff+1<<'\n';
        }
    }
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Incorrect 94 ms 28080 KB Output isn't correct
3 Incorrect 47 ms 28104 KB Output isn't correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Incorrect 1 ms 4956 KB Output isn't correct
6 Incorrect 1 ms 4944 KB Output isn't correct
7 Incorrect 2 ms 4956 KB Output isn't correct
8 Incorrect 2 ms 4952 KB Output isn't correct
9 Incorrect 6 ms 7260 KB Output isn't correct
10 Incorrect 18 ms 10456 KB Output isn't correct
11 Incorrect 94 ms 28052 KB Output isn't correct
12 Incorrect 48 ms 28064 KB Output isn't correct
13 Incorrect 92 ms 28080 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 14364 KB Output isn't correct
2 Incorrect 113 ms 39880 KB Output isn't correct
3 Incorrect 55 ms 37632 KB Output isn't correct
4 Incorrect 61 ms 16340 KB Output isn't correct
5 Incorrect 54 ms 16340 KB Output isn't correct
6 Incorrect 51 ms 15956 KB Output isn't correct
7 Incorrect 55 ms 15828 KB Output isn't correct
8 Incorrect 30 ms 14524 KB Output isn't correct
9 Incorrect 120 ms 39980 KB Output isn't correct
10 Incorrect 115 ms 39872 KB Output isn't correct
11 Incorrect 89 ms 38996 KB Output isn't correct
12 Incorrect 115 ms 38520 KB Output isn't correct
13 Incorrect 61 ms 39080 KB Output isn't correct
14 Incorrect 56 ms 37904 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 24012 KB Output isn't correct
2 Incorrect 138 ms 39856 KB Output isn't correct
3 Incorrect 84 ms 36052 KB Output isn't correct
4 Incorrect 76 ms 34216 KB Output isn't correct
5 Incorrect 86 ms 34176 KB Output isn't correct
6 Incorrect 80 ms 34248 KB Output isn't correct
7 Incorrect 76 ms 33228 KB Output isn't correct
8 Incorrect 80 ms 36108 KB Output isn't correct
9 Incorrect 134 ms 41136 KB Output isn't correct
10 Incorrect 142 ms 41012 KB Output isn't correct
11 Incorrect 142 ms 41016 KB Output isn't correct
12 Incorrect 146 ms 39832 KB Output isn't correct
13 Incorrect 141 ms 43208 KB Output isn't correct
14 Execution timed out 1069 ms 35084 KB Time limit exceeded

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 40220 KB Output isn't correct
2 Incorrect 132 ms 39876 KB Output isn't correct
3 Incorrect 65 ms 41932 KB Output isn't correct
4 Incorrect 146 ms 40052 KB Output isn't correct
5 Incorrect 123 ms 39872 KB Output isn't correct
6 Incorrect 87 ms 39120 KB Output isn't correct
7 Incorrect 138 ms 39880 KB Output isn't correct
8 Incorrect 66 ms 41928 KB Output isn't correct
9 Incorrect 53 ms 37636 KB Output isn't correct