글 읽기 - 스포주의

shjohw12 2년 전 3

끝 인덱스 예외처리해줘야하네요 ㅋㅋㅋ끝 인덱스 예외처리해줘야하네요 ㅋㅋㅋ끝 인덱스 예외처리해줘야하네요 ㅋㅋㅋ끝 인덱스 예외처리해줘야하네요 ㅋㅋㅋ끝 인덱스 예외처리해줘야하네요 ㅋㅋㅋ

lms062111 2년 전 0

혹시 계속 시간 초과가 나는데 이유 알 수 있을까요,,?

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int dp[10001] = {0};
struct Node{
    int data;
    int count;
    map<int, Node*> nextChild;

    Node(int data = 0){
        this->data = data;
        this->count = 0;
    }
};

void add(Node * root,vector<int> newNode){
    Node * parent = root;
    for(int next : newNode){
        if(parent->nextChild.find(next) == parent->nextChild.end()){
            Node *newNode = new Node;
            newNode->data = next;
            newNode->count = 0;    
            parent->nextChild.insert({next,newNode});
        }
        parent = parent->nextChild[next];

    }
    parent->count += 1;

}

void travel(Node * root){
    Node * parent = root;
    int count_sum = 0;
    int count_square = 0;
    map<int,Node*> ::iterator iter;
    if(parent){
        for(iter = parent->nextChild.begin();iter != parent->nextChild.end();iter++){
            travel(iter->second);
            count_sum += iter->second->count;
            count_square += (iter->second->count) * (iter->second->count);

        }
        parent->count += count_sum;
        dp[parent->data] += (count_sum*count_sum - count_square) / 2;
    }
}

int main(void){
    int n,q;
    cin >> n ;
    cin >> q;
    
    Node root = Node(0);
    
    for (int i = 0; i < n; i++)
    {
        vector<int> newNode;
        int k;
        int temp;
        cin >> k;
        for (int i = 0; i < k; i++)
        {   
            cin >> temp;
            newNode.push_back(temp);
        }

        add(&root,newNode);
        
    }
    travel(&root);

    for (int i = 0; i < q; i++)
    {
        int temp;
        cin >> temp;
        cout << dp[temp] << "\n";
    }
    

}

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

문제

문제

출처

ICPC

스포주의

shjohw12 2년 전 3

lms062111 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말