oj.uz

답안 #100744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100744 2019-03-13T20:23:27 Z shafinalam Ball Machine (BOI13_ballmachine) C++14
100 / 100
 619 ms 31608 KB 
#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[left]>=k) return kth(left, b, mid, k);
    else return kth(right, mid+1, e, k-(x-tree[left]));
}
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

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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11392 KB Output is correct
2 Correct 242 ms 15096 KB Output is correct
3 Correct 124 ms 14840 KB Output is correct
4 Correct 11 ms 11264 KB Output is correct
5 Correct 11 ms 11264 KB Output is correct
6 Correct 13 ms 11392 KB Output is correct
7 Correct 11 ms 11392 KB Output is correct
8 Correct 11 ms 11392 KB Output is correct
9 Correct 19 ms 11648 KB Output is correct
10 Correct 38 ms 12160 KB Output is correct
11 Correct 169 ms 14968 KB Output is correct
12 Correct 120 ms 14844 KB Output is correct
13 Correct 178 ms 14832 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 14968 KB Output is correct
2 Correct 425 ms 23964 KB Output is correct
3 Correct 152 ms 16688 KB Output is correct
4 Correct 154 ms 15224 KB Output is correct
5 Correct 197 ms 15224 KB Output is correct
6 Correct 207 ms 15096 KB Output is correct
7 Correct 187 ms 14036 KB Output is correct
8 Correct 93 ms 15196 KB Output is correct
9 Correct 346 ms 23888 KB Output is correct
10 Correct 378 ms 23928 KB Output is correct
11 Correct 352 ms 23288 KB Output is correct
12 Correct 402 ms 20216 KB Output is correct
13 Correct 220 ms 28424 KB Output is correct
14 Correct 148 ms 16688 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 17788 KB Output is correct
2 Correct 619 ms 20896 KB Output is correct
3 Correct 311 ms 27640 KB Output is correct
4 Correct 264 ms 21700 KB Output is correct
5 Correct 308 ms 21704 KB Output is correct
6 Correct 280 ms 21760 KB Output is correct
7 Correct 271 ms 18936 KB Output is correct
8 Correct 258 ms 27512 KB Output is correct
9 Correct 381 ms 24440 KB Output is correct
10 Correct 495 ms 24608 KB Output is correct
11 Correct 442 ms 24588 KB Output is correct
12 Correct 413 ms 21040 KB Output is correct
13 Correct 403 ms 31608 KB Output is correct
14 Correct 199 ms 17840 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 24192 KB Output is correct
2 Correct 367 ms 20776 KB Output is correct
3 Correct 227 ms 30564 KB Output is correct
4 Correct 376 ms 24276 KB Output is correct
5 Correct 457 ms 24160 KB Output is correct
6 Correct 435 ms 23476 KB Output is correct
7 Correct 456 ms 20600 KB Output is correct
8 Correct 231 ms 30584 KB Output is correct
9 Correct 150 ms 16688 KB Output is correct