oj.uz

답안 #92137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92137 2019-01-01T15:46:16 Z luckyboy Ball Machine (BOI13_ballmachine) C++14
100 / 100
 318 ms 21496 KB 
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 100005
#define maxm 1000006
#define pii pair <int,int>
#define Task ""
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,q,t[maxn << 2],lz[maxn << 2],cnt,out[maxn],pos[maxn],mi[maxn],root,par[maxn][17];
vector <int> a[maxn];
bool comp(int x,int y)
{
    return mi[x] < mi[y];
}
void Pre_Dfs(int u)
{
    mi[u] = u;
    for (int v : a[u])
    {
        Pre_Dfs(v);
        mi[u] = min(mi[u],mi[v]);
    }
}
void Dfs(int u)
{
    for (int v : a[u])
    {
        par[v][0] = u;
        FOR(i,1,16)
            par[v][i] = par[par[v][i-1]][i-1];
        Dfs(v);
    }
    out[u] = ++cnt;
    pos[cnt] = u;
}
int Find(int l,int r,int id,int remain)
{
    if (l == r) return l;
    int mid = (l+r) >> 1;
    if (mid - l + 1 - t[2*id] >= remain) return Find(l,mid,2*id,remain);
    return Find(mid+1,r,2*id+1,remain - (mid - l + 1 - t[2*id]));
}
void Push(int l,int r,int id)
{
    if (lz[id] != -1)
    {
        int mid = (l+r) >> 1;
        lz[2*id] = lz[2*id+1] = lz[id];
        t[2*id] = (mid - l + 1) * lz[id];
        t[2*id+1] = (r - mid) * lz[id];
        lz[id] = -1;
    }
}
void Update(int l,int r,int id,int u,int v,int val)
{
    if (l > v || r < u) return;
    if (u <= l && r <= v)
    {
        t[id] = (r - l + 1) * val;
        lz[id] = val;
        return;
    }
    Push(l,r,id);
    int mid = (l+r) >> 1;
    Update(l,mid,2*id,u,v,val);
    Update(mid+1,r,2*id+1,u,v,val);
    t[id] = t[2*id+1] + t[2*id];
}
int Get(int l,int r,int id,int x)
{
    if (l == r) return t[id];
    Push(l,r,id);
    int mid = (l+r) >> 1;
    if (mid >= x) return Get(l,mid,2*id,x);
    return Get(mid+1,r,2*id+1,x);
}
int main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n >> q;
    FOR(i,1,n << 2) lz[i] = -1;
    FOR(i,1,n)
    {
        int x;
        cin >> x;
        if (!x) root = i;
        else a[x].pb(i);
    }
    Pre_Dfs(root);
    FOR(i,1,n) sort(a[i].begin(),a[i].end(),comp);
    Dfs(root);
    while (q--)
    {
        int type,x;
        cin >> type >> x;
        if (type & 1)
        {
            int ww = Find(1,n,1,x);
            cout << pos[ww] << '\n';
            Update(1,n,1,1,ww,1);
        }
        else
        {
            int ans = 0;
            FORD(i,16,0)
            {
                int nex = par[x][i];
                if (!nex || !Get(1,n,1,out[nex])) continue;
                ans += 1 << i;
                x = nex;
            }
            Update(1,n,1,out[x],out[x],0);
            cout << ans << '\n';
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 129 ms 10616 KB Output is correct
3 Correct 72 ms 10384 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 10 ms 3264 KB Output is correct
10 Correct 24 ms 4600 KB Output is correct
11 Correct 131 ms 10488 KB Output is correct
12 Correct 75 ms 10348 KB Output is correct
13 Correct 103 ms 10104 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 6136 KB Output is correct
2 Correct 292 ms 17372 KB Output is correct
3 Correct 90 ms 13684 KB Output is correct
4 Correct 114 ms 7624 KB Output is correct
5 Correct 143 ms 7280 KB Output is correct
6 Correct 125 ms 7032 KB Output is correct
7 Correct 119 ms 6520 KB Output is correct
8 Correct 51 ms 6136 KB Output is correct
9 Correct 256 ms 17580 KB Output is correct
10 Correct 318 ms 17308 KB Output is correct
11 Correct 252 ms 16760 KB Output is correct
12 Correct 230 ms 15708 KB Output is correct
13 Correct 154 ms 18296 KB Output is correct
14 Correct 91 ms 13620 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 10388 KB Output is correct
2 Correct 276 ms 16732 KB Output is correct
3 Correct 195 ms 17656 KB Output is correct
4 Correct 160 ms 15036 KB Output is correct
5 Correct 204 ms 14640 KB Output is correct
6 Correct 185 ms 14732 KB Output is correct
7 Correct 178 ms 13688 KB Output is correct
8 Correct 207 ms 17636 KB Output is correct
9 Correct 250 ms 18400 KB Output is correct
10 Correct 300 ms 17756 KB Output is correct
11 Correct 306 ms 17880 KB Output is correct
12 Correct 289 ms 16592 KB Output is correct
13 Correct 309 ms 21496 KB Output is correct
14 Correct 138 ms 14656 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 17912 KB Output is correct
2 Correct 295 ms 16376 KB Output is correct
3 Correct 157 ms 20332 KB Output is correct
4 Correct 266 ms 17912 KB Output is correct
5 Correct 310 ms 17400 KB Output is correct
6 Correct 244 ms 16888 KB Output is correct
7 Correct 277 ms 16344 KB Output is correct
8 Correct 164 ms 20344 KB Output is correct
9 Correct 83 ms 13684 KB Output is correct