oj.uz

답안 #203204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203204 2020-02-19T19:55:10 Z mdn2002 Ball Machine (BOI13_ballmachine) C++14
39.0659 / 100
 1000 ms 61916 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,rt,st[100500],fn[100500],tim=1,mn[100500],on[100500],spt[100500][30],dp[100500];
vector<int>gr[100500];
set<pair<int,int> >s;
void dfs(int x)
{
    mn[x]=x;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        dfs(u);
        mn[x]=min(mn[x],mn[u]);
    }
}
void dfs1(int x,int p)
{
    spt[x][0]=p;
    dp[x]=dp[p]+1;
    st[x]=tim++;
    vector<pair<int,int> >v;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        v.push_back({mn[u],u});
    }
    sort(v.begin(),v.end());
    for(int i=gr[x].size()-1; i>=0; i--)
    {
        int u=v[i].second;
        dfs1(u,x);
    }
    fn[x]=tim;
}
bool ck(int x,int mid)
{
    int dif=mid;
    if(dif>dp[x])return 0;
    for(int i=0; i<=21; i++)
    {
        if((dif&(1<<i)))x=spt[x][i];
    }
    if(on[x]==0)return 0;
    else return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        if(x==0)
        {
            rt=i;
            continue;
        }
        gr[x].push_back(i);
    }
    dfs(rt);
    dfs1(rt,0);
    for(int i=1; i<=n; i++)s.insert({st[i],i});
    for(int i=1; i<=25; i++)
    {
        for(int j=1; j<=n; j++)spt[j][i]=spt[spt[j][i-1]][i-1];
    }
    while(m--)
    {
        int t,x;
        cin>>t>>x;
        if(t==1)
        {
            int to;
            while(x--)
            {
                pair<int,int>z=*--s.end();
                s.erase(--s.end());
                to=z.second;
                on[to]++;
            }
            cout<<to<<endl;
        }
        else
        {
            int l=0,r=n,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                if(ck(x,mid))l=mid+1;
                else r=mid;
            }
            cout<<l-1<<endl;
            int dif=l-1;
            for(int i=0; i<=21; i++)
            {
                if((dif&(1<<i)))x=spt[x][i];
            }
            on[x]=0;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs1(int, int)':
ballmachine.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:81:19: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<to<<endl;
                   ^~

Subtask #1
1.92307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 5368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 318 ms 32764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 406 ms 17340 KB Output isn't correct
4 Runtime error 11 ms 5368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 5368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 18 ms 2936 KB Output is correct
7 Runtime error 12 ms 5752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 16 ms 5752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 22 ms 7032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 80 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 245 ms 32864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 445 ms 17308 KB Output isn't correct
13 Runtime error 327 ms 33016 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 168 ms 18552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 724 ms 60924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 418 ms 23784 KB Output isn't correct
4 Runtime error 173 ms 22264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 100 ms 21752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 218 ms 22240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 119 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 169 ms 18548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 447 ms 61304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 730 ms 60940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 783 ms 61100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 680 ms 53496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Incorrect 513 ms 34296 KB Output isn't correct
14 Incorrect 415 ms 23840 KB Output isn't correct

Subtask #3
37.1428571429 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 17148 KB Output is correct
2 Correct 870 ms 28128 KB Output is correct
3 Correct 717 ms 31224 KB Output is correct
4 Correct 560 ms 25628 KB Output is correct
5 Correct 610 ms 25260 KB Output is correct
6 Correct 557 ms 25224 KB Output is correct
7 Correct 556 ms 22960 KB Output is correct
8 Correct 768 ms 31352 KB Output is correct
9 Correct 769 ms 31708 KB Output is correct
10 Correct 849 ms 31104 KB Output is correct
11 Correct 901 ms 31224 KB Output is correct
12 Correct 805 ms 28048 KB Output is correct
13 Execution timed out 1096 ms 38776 KB Time limit exceeded
14 Correct 463 ms 24144 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 797 ms 61748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 669 ms 54648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 509 ms 38424 KB Output isn't correct
4 Runtime error 766 ms 61916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 575 ms 61048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 690 ms 61172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 674 ms 54776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 521 ms 38396 KB Output isn't correct
9 Incorrect 414 ms 23884 KB Output isn't correct