oj.uz

답안 #106309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106309 2019-04-17T20:48:31 Z RedNextCentury Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 44152 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000000];
int mn[1000000];
bool cmp(int a,int b)
{
    return mn[a]<mn[b];
}
void pre(int v)
{
    mn[v]=v;
    for (auto u:adj[v])
    {
        pre(u);
        mn[v]=min(mn[v],mn[u]);
    }
}
int pa[1000001][21];
int ord[1000001];
int tt=1;
void dfs(int v)
{
    for (auto u:adj[v])
        dfs(u);
    ord[v]=tt++;
}
bool has[1000000];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    int root=-1;
    for (int i=1;i<=n;i++)
    {
        cin>>pa[i][0];
        if (pa[i][0]==0) root = i;
        else adj[pa[i][0]].push_back(i);
    }
    for (int j=1;j<=18;j++)
        for (int i=1;i<=n;i++)
            pa[i][j]=pa[pa[i][j-1]][j-1];
    for (int i=1;i<=n;i++)
        sort(adj[i].begin(),adj[i].end(),cmp);
    dfs(root);
    set<pair<int,int> > s;
    for (int i=1;i<=n;i++)
        s.insert({ord[i],i});
    while(q--)
    {
        int t,v;
        cin>>t>>v;
        if (t==1)
        {
            pair<int,int> p;
            while(v--)
            {
                p = *s.begin();
                s.erase(s.begin());
                has[p.second]=1;
            }
            cout<<p.second<<endl;
        }
        else
        {
            int u = v;
            int ret=0;
            for (int i=18;i>=0;i--)
                if (has[pa[u][i]])
                    u = pa[u][i] , ret+=(1<<i);
            has[u]=0;
            s.insert({ord[u],u});
            cout<<ret<<endl;
        }
    }
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 23936 KB Output isn't correct
2 Execution timed out 1054 ms 33728 KB Time limit exceeded
3 Incorrect 292 ms 34016 KB Output isn't correct
4 Execution timed out 1068 ms 23800 KB Time limit exceeded
5 Incorrect 22 ms 23936 KB Output isn't correct
6 Incorrect 25 ms 23936 KB Output isn't correct
7 Execution timed out 1077 ms 24064 KB Time limit exceeded
8 Execution timed out 1040 ms 23928 KB Time limit exceeded
9 Incorrect 46 ms 24448 KB Output isn't correct
10 Execution timed out 1081 ms 26308 KB Time limit exceeded
11 Incorrect 350 ms 33892 KB Output isn't correct
12 Incorrect 231 ms 34084 KB Output isn't correct
13 Incorrect 270 ms 33980 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 27640 KB Output is correct
2 Incorrect 407 ms 41268 KB Output isn't correct
3 Incorrect 268 ms 38976 KB Output isn't correct
4 Execution timed out 1066 ms 29176 KB Time limit exceeded
5 Execution timed out 1075 ms 28920 KB Time limit exceeded
6 Incorrect 207 ms 29176 KB Output isn't correct
7 Incorrect 236 ms 28536 KB Output isn't correct
8 Correct 172 ms 27864 KB Output is correct
9 Incorrect 363 ms 41436 KB Output isn't correct
10 Incorrect 442 ms 41228 KB Output isn't correct
11 Incorrect 364 ms 41028 KB Output isn't correct
12 Incorrect 393 ms 39996 KB Output isn't correct
13 Correct 342 ms 41620 KB Output is correct
14 Incorrect 260 ms 39028 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 32636 KB Output isn't correct
2 Incorrect 427 ms 40472 KB Output isn't correct
3 Correct 260 ms 39928 KB Output is correct
4 Incorrect 268 ms 38024 KB Output isn't correct
5 Incorrect 279 ms 37564 KB Output isn't correct
6 Incorrect 280 ms 37600 KB Output isn't correct
7 Incorrect 262 ms 36984 KB Output isn't correct
8 Correct 271 ms 40016 KB Output is correct
9 Incorrect 415 ms 41592 KB Output isn't correct
10 Incorrect 462 ms 41164 KB Output isn't correct
11 Incorrect 493 ms 41200 KB Output isn't correct
12 Incorrect 479 ms 40312 KB Output isn't correct
13 Correct 421 ms 44152 KB Output is correct
14 Incorrect 421 ms 38900 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 442 ms 41620 KB Output isn't correct
2 Incorrect 434 ms 40476 KB Output isn't correct
3 Correct 323 ms 43884 KB Output is correct
4 Incorrect 387 ms 41592 KB Output isn't correct
5 Incorrect 368 ms 41080 KB Output isn't correct
6 Incorrect 312 ms 41080 KB Output isn't correct
7 Incorrect 378 ms 40312 KB Output isn't correct
8 Correct 289 ms 43896 KB Output is correct
9 Incorrect 250 ms 39152 KB Output isn't correct