글 읽기 - 메모리 초과가 발생하는 이유를 알고 싶습니다....

wnsgur1714 4년 전 0

HLD에 세그먼트 트리를 사용했구요. 메모리 초과가 왜 일어나는지 아무리 생각해봐도 모르겠습니다ㅠㅠ

#include <bits/stdc++.h>

using namespace std;

struct node{
    int bumo;
    int dept;
    int weigt;
    int ign;
    int ig;
};

int n, r;
vector<node> tree;
vector<vector<int> > edge;
vector<vector<int> > grup;
vector<vector<long long int> > st;
int grupn;
bool visited[200001];
bool vvisited[200001];

int bdw(int now, int dep){
    tree[now].weigt = 1;
    visited[now] = true;
    tree[now].dept = dep;
    for(int i = 0 ; i < edge[now].size() ; i++){
        if(visited[edge[now][i]] == false){
            tree[edge[now][i]].bumo = now;
            tree[now].weigt += bdw(edge[now][i], dep+1);
        }
    }
    return tree[now].weigt;
}

void mtg(int now, int gn){
    vvisited[now] = true;
    grup[gn].push_back(now);
    tree[now].ig = gn;
    tree[now].ign = grup[gn].size();
    int maxx = 0;
    int mn = 0;
    for(int i = 0 ; i < edge[now].size() ; i++){
        if(vvisited[edge[now][i]] == false){
            if(tree[edge[now][i]].weigt > maxx){
                if(maxx != 0){
                    grupn++;
                    mtg(edge[now][mn], grupn);
                }
                maxx = tree[edge[now][i]].weigt;
                mn = i;
            }
            else{
                grupn++;
                mtg(edge[now][i], grupn);
            }
        }
    }
    if(maxx != 0){
        mtg(edge[now][mn], gn);
    }
}

void ctst(int node, int start, int endd, int ntc, int gr){
    if(start == endd){
        st[gr][node]++;
    }
    else{
        int mid = (start+endd)/2;
        if(mid >= ntc){
            ctst(node*2, start, mid, ntc, gr);
        }
        else{
            ctst(node*2+1, mid+1, endd, ntc, gr);
        }
        st[gr][node] = st[gr][node*2] + st[gr][node*2+1];
    }
}

int fist(int node, int start, int endd, int nts, int ntd, int gr){
    if(nts > endd || ntd < start){
        return 0;
    }
    else if(start >= nts && endd <= ntd){
        return st[gr][node];
    }
    else{
        int mid = (start+endd)/2;
        return fist(node*2, start, mid, nts, ntd, gr) + fist(node*2+1, mid+1, endd, nts, ntd, gr);
    }
}

void ctn(int w){
    if(tree[w].ig == tree[1].ig){
        ctst(1, 1, grup[tree[w].ig].size(), tree[w].ign, tree[w].ig);
    }
    else{
        while(tree[w].ig != tree[1].ig){
            ctst(1, 1, grup[tree[w].ig].size(), tree[w].ign, tree[w].ig);
            w = tree[grup[tree[w].ig][0]].bumo;
        }
    }
}

int fdn(int ntf){
    return fist(1, 1, grup[tree[ntf].ig].size(), tree[ntf].ign, grup[tree[ntf].ig].size(), tree[ntf].ig);
}

void doq(){
    int q;
    cin >> q;
    for(int i = 0 ; i < q; i++){
        int a, b;
        cin >> a >> b;
        if(a == 1){
            ctn(b);
        }
        else{
            cout << fdn(b)*(long long int)tree[b].dept << "\n";
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> r;
    edge.resize(n+1);
    tree.resize(n+1);
    grup.resize(n+1);
    for(int i = 1 ; i < n ; i++){
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    tree[1].bumo = 0;
    bdw(r, 1);
    grupn = 1;
    mtg(r, grupn);
    st.resize(grupn+1);
    for(int i = 1 ; i <= grupn ; i++){
        st[i].resize(grup[i].size()*10);
    }
    doq();
}

/*해야 할 것:
(1. 각 정점마다 부모, 깊이, 무게 구하기) SOLVED;
(2. 구역 분리, 각 정점마다 구역과 해당 구역에서의 번호 저장) SOLVED;
(3. 각 구역마다 세그먼트 트리 할당) SOLVED;
4. 쿼리 실행
   -1 1부터 a까지의 경로의 모든 구역의 세그먼트 트리 갱신
   -2 해당 구역의 끝부터 a까지의 세그먼트 트리 값x해당 정점의 깊이*/

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과가 발생하는 이유를 알고 싶습니다....

wnsgur1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말