THE100YEARSWAR 문제 시간초과

  • ansy1219
    ansy1219
    #include <iostream>
    #include <queue>
    #include <vector>
    #include <list>
    
    using namespace std;
    
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            int n, q;
    
            cin >> n >> q;
    
            int *parent = (int*)calloc(n + 1, sizeof(int));
            int *team = (int*)calloc(n + 1, sizeof(int));
            vector<list<int>> child;
            child.resize(n + 1);
    
            parent[1] = -1;
            parent[2] = -1;
            team[1] = 1;
            team[2] = 2;
    
            for (int i = 0; i < n - 2; i++)
            {
                int a, b;
                cin >> a >> b;
                parent[b] = a;
                child[a].push_back(b);
                team[b] = team[a];
            }
    
    
            for (int i = 0; i < q; i++)
            {
                char tq;
                int a, b;
                cin >> tq;
                if (tq == 'T')
                {
                    cin >> a;
    
                    queue<int> search;
                    search.push(a);
                    while (!search.empty())
                    {
                        int p = search.front();
                        search.pop();
    
                        if (team[p] == 1)
                        {
                            team[p] = 2;
                        }
                        else
                            team[p] = 1;
    
                        for (list<int>::iterator it = child[p].begin(); it != child[p].end(); it++)
                        {
                            search.push(*it);
                        }
                    }
                }
                else
                {
                    cin >> a >> b;
                    if (team[a] == team[b])
                        cout << "Ally\n";
                    else
                        cout << "Enemy\n";
                }
            }
    
        }
    
        return 0;
    }
    

    어느 부분이 시간을 많이 잡아먹는지 감을 못잡겠네요 ㅜ
    혹시 큐나 리스트가 시간을 많이 잡아먹나요?


    8년 전
1개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    네, 해당 문제는 별도의 자료구조를 이용하는것이 출제 취지였습니다


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.