Submission #100740

#	Time	Username	Problem	Language	Result	Execution time	Memory
100740		shafinalam	Ball Machine (BOI13_ballmachine)	C++14	16.23 / 100	524 ms	31736 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5+5;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

#define  sf scanf
#define  pf printf

#define  input freopen("input.txt","r",stdin)
#define  output freopen("output.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))

int  Set(int N,int pos){return N=N | (1<<pos);}
int  reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}

vector<int>adj[mx];
int choto[mx];
int lev[mx];
int fin[mx];
int pos[mx];
int spar[mx][18];
int tree[mx<<2];
int lazy[mx<<2];
int tym = 0;
int n, m;

bool cmp(int a, int b)
{
    return choto[a]<choto[b];
}
int dfs(int u, int p, int dep)
{
    lev[u] = dep;
    choto[u] = u;
    for(int i = 0; i < adj[u].size(); i++)
    {
        int v = adj[u][i];
        if(v==p) continue;
        spar[v][0] = u;
        choto[u] = min(choto[u], dfs(v, u, dep+1));
    }
    return choto[u];
}
void dfs2(int u, int p)
{
    vector<int>child;
    for(int i = 0; i < adj[u].size(); i++)
    {
        int v = adj[u][i];
        if(v==p) continue;
        child.push_back(v);
    }
    sort(all(child), cmp);
    for(int i = 0; i < child.size(); i++)
    {
        int v = child[i];
        dfs2(v, u);
    }
    fin[u] = ++tym;
    pos[tym] = u;
}
void build()
{
    for(int j = 1; j <= 17; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(spar[i][j-1]!=-1) spar[i][j] = spar[spar[i][j-1]][j-1];
        }
    }
    return;
}
void duka(int node, int b, int e)
{
    if(lazy[node]==-1) return;
    int left = node<<1;
    int right = left|1;
    if(b!=e)lazy[left] = lazy[right] = lazy[node];
    tree[node] = ((e-b+1)*lazy[node]);
    lazy[node] = -1;
}
void update(int node, int b, int e, int l, int r, int val)
{
    duka(node, b, e);
    if(b>r || e<l) return;
    if(b>=l && e<=r)
    {
        lazy[node] = val;
        duka(node, b, e);
        return;
    }
    int left = node<<1;
    int right = left|1;
    int mid = (b+e)>>1;
    update(left, b, mid, l, r, val);
    update(right, mid+1, e, l, r, val);
    tree[node] = tree[left]+tree[right];
}
int query(int node, int b, int e, int pos)
{
    duka(node, b, e);
    if(b==e) return tree[node];
    int left = node<<1;
    int right = left|1;
    int mid = (b+e)>>1;
    if(pos<=mid) return query(left, b, mid, pos);
    else return query(right, mid+1, e, pos);
}
int kth(int node, int b, int e, int k)
{
    duka(node, b, e);
    if(b==e) return b;
    int left = node<<1;
    int right = left|1;
    int mid = (b+e)>>1;
    int x = mid-b+1;
    if(x-tree[node]>=k) return kth(left, b, mid, k);
    else return kth(right, mid+1, e, k-tree[node]);
}
int main()
{
    sf("%d%d", &n, &m);

    int root = 0;
    for(int i = 1; i <= n; i++)
    {
        int x;
        sf("%d", &x);
        if(x==0) root = i;
        else
        {
            adj[i].push_back(x);
            adj[x].push_back(i);
        }
    }
    memset(spar, -1, sizeof spar);
    memset(lazy, -1, sizeof lazy);
    dfs(root, 0, 1);
    dfs2(root, 0);
    build();

    while(m--)
    {
        int op;
        sf("%d", &op);

        if(op==1)
        {
            int k;
            sf("%d", &k);

            int x = kth(1, 1, n, k);
            update(1, 1, n, 1, x, 1);
            pf("%d\n", pos[x]);
        }
        else
        {
            int x;
            sf("%d", &x);

            int u = x;

            for(int i = 17; i >= 0; i--)
            {
                if(spar[u][i]!=-1 && query(1, 1, n, fin[spar[u][i]])==1) u = spar[u][i];
            }
            update(1, 1, n, fin[u], fin[u], 0);
            pf("%d\n", abs(lev[x]-lev[u]));
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int dfs(int, int, int)':
ballmachine.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++)
                    ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(int, int)':
ballmachine.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++)
                    ~~^~~~~~~~~~~~~~~
ballmachine.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < child.size(); i++)
                    ~~^~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     sf("%d%d", &n, &m);
       ^
ballmachine.cpp:146:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         sf("%d", &x);
           ^
ballmachine.cpp:163:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         sf("%d", &op);
           ^
ballmachine.cpp:168:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             sf("%d", &k);
               ^
ballmachine.cpp:177:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             sf("%d", &x);
               ^

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.6666666666666667 / 5