제출 #667120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667120		ar_paixaos19	Ball Machine (BOI13_ballmachine)	C++14	컴파일 에러	0 ms	0 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 100010;
const int LOGN = 20;
 
struct node{
    int sum, lz;
 
    node(){
        sum = 0;
        lz = -1;
    }
};
 
int t = 0;
int tin[MAXN], tout[MAXN], submin[MAXN], posicao[MAXN], pai[MAXN], dist[MAXN];
node seg[4 * MAXN];
int up[LOGN+10][MAXN];
vector<int> grafo[MAXN];
 
bool cmp(int i, int j){
    return submin[i] < submin[j];
}
 
 
void dfs(int v, int p, int id){
 
    submin[v] = v;
    for(auto viz : grafo[v]){
        if(viz == p) continue;
        dist[viz] = dist[v] + 1;
        dfs(viz, v, id);
        submin[v] = min(submin[v], submin[viz]);
    }
 
    if(id == 1){
        tout[v] = ++t;
        posicao[t] = v;
        return;
    }
    for(int i = 0; i < grafo[v].size(); i++){
        sort(grafo[v].begin(), grafo[v].end(), cmp);
    }
 
    return;
}
 
void refresh(int pos, int ini, int fim){
    if(seg[pos].lz == -1){
        //printf("deu em %d\n", pos);
        return;
    }
    if(ini == fim){
        seg[pos].sum = seg[pos].lz;
        seg[pos].lz = -1;
        return;
    }
    int e = 2 * pos, d = 2 * pos + 1;
 
    seg[e].lz = seg[pos].lz;
    seg[d].lz = seg[pos].lz;
 
    seg[pos].sum = (fim - ini + 1) * seg[pos].lz;
    seg[pos].lz = -1;
    return;
}
 
void update(int pos, int ini, int fim, int l, int r, int val){
    refresh(pos, ini, fim);
    if(ini > r || fim < l) return;
    if(l <= ini && fim <= r){
        seg[pos].lz = val;
        refresh(pos, ini, fim);
        return;
    }
 
    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;
 
    update(e, ini, m, l, r, val);
    update(d, m + 1, fim, l, r, val);
 
    seg[pos].sum = seg[e].sum + seg[d].sum;
    return;
}
 
int bsseg(int pos, int ini, int fim, int s){
    if(ini == fim){
        return ini;
    }
    //refresh(pos, ini, fim);
 
    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;
 
    refresh(e, ini, m), refresh(d, m + 1, fim);
 
    if(seg[e].sum >= s) return bsseg(e, ini, m, s);
    return bsseg(d, m + 1, fim, s - seg[e].sum);
}
 
int query(int pos, int ini, int fim, int id){
    if(id < ini || id > fim) return 0;
    if(seg[pos].lz != -1){
        int resp = seg[pos].lz;
        refresh(pos, ini, fim);
        return resp;
    }
    refresh(pos, ini, fim);
    if(ini == fim) return seg[pos].sum;
 
    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;
    if(id <= m) return query(e, ini, m, id);
    return query(d, m + 1, fim, id);
}
 
void calcup(int n){
    for(int i = 1; i <= n; i++){
        up[0][i] = pai[i];
    }
 
    for(int k = 1; k < LOGN; k++){
        for(int i = 1; i <= n; i++){
            up[k][i] = up[k - 1][ up[k - 1][i] ];
        }
    }
 
    return;
}
 
int bsbl(int v, int n){
    for(int k = LOGN - 1; k >= 0; k--){
        int l = tout[ up[k][v] ];
        if(!query(1, 1, n, l)){
            //printf("deu no k = %d\n", k);
            v = up[k][v];
        }
    }
 
    return v;
}
 
template<typename T> void read(T& aa)
{
	aa=0;
	char cc=getchar();
	T ff=1;
 
	while((cc != '-') && (cc < '0' || cc > '9')) cc=getchar();
 
	if(cc=='-') ff=-1, cc=getchar();
 
	while(cc >= '0' && cc <= '9') aa = aa*10 + cc - '0', cc=getchar();
	aa*=ff;
}
 
int main(){
  cin.tie(0)->sync_with_stdio(0);
    int n, q; read(n), read(q);
    int root;
    update(1, 1, n, 1, n, 1);
    for(int i = 1; i <= n; i++){
        int v; read(v);
        if(v == 0){
            root = i;
            pai[root] = root;
            continue;
        }
 
        pai[i] = v;
        grafo[i].push_back(v);
        grafo[v].push_back(i);
    }
 
    dfs(root, root, 0);
    dfs(root, root, 1);
    calcup(n);
 
    for(int i = 1; i <= q; i++){
        int type; read(type);
 
        if(type == 1){
            int k; read(k);
 
            int t = bsseg(1, 1, n, k);
            cout << posicao[t] << '\n';
            update(1, 1, n, 1, t, 0);
        }
        if(type == 2){
            int x; read(x);
 
            int r = bsbl(x, n);
            cout <<  dist[x] - dist[r] << '\n';
            update(1, 1, n, tout[r], tout[r], 1);
        }
    }

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'void dfs(int, int, int)':
ballmachine.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < grafo[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:198:5: error: expected '}' at end of input
  198 |     }
      |     ^
ballmachine.cpp:159:11: note: to match this '{'
  159 | int main(){
      |           ^