FORTRESS 어떤부분이 잘못된건가요?(예제는 돌아갑니다)

  • whatugonnado
    whatugonnado

    FORTRESS

    • 반지름 크기가 작은 것부터 정렬후
    • 순서대로 트리를 만들면서 first와 second를 축척하면서 비교하고 있습니다
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <algorithm>
    #include <array>
    #include <bitset>
    #include <cmath>
    using namespace std;
    
    //typedef unsigned int uint32_t;
    // 내 리프의 최대 경로
    // 현재위치의 최대경로 first + second + 1
    array<pair<uint32_t, uint32_t>, 101> MyMax;
    
    struct Tree {
        uint32_t x, y, r;
    };
    array<Tree, 101> MyTree;
    //bitset<101> IsUsed;
    uint32_t N, maxValue;
    
    //return true, if b was bigger than a
    bool cmp(Tree& a, Tree& b) {
        return a.r < b.r;
    }
    
    bool IsInSide(Tree& leaf, Tree& root) {
        return ((root.r - leaf.r)*(root.r - leaf.r) >
            (root.x - leaf.x)*(root.x - leaf.x) + (root.y - leaf.y)*(root.y - leaf.y));
    }
    
    inline uint32_t themax(uint32_t l, uint32_t r) {
        if (l > r)
            return l;
        return r;
    }
    
    uint32_t FORTRESS_play(uint32_t startIndex){
        for (uint32_t i = startIndex + 1; i < N; ++i) {
            //cmp가 없어도 될 수 도 있다.
            if (cmp(MyTree[startIndex], MyTree[i]) && IsInSide(MyTree[startIndex], MyTree[i])) {
                cout << startIndex << "->" << i << endl;
                if (MyMax[i].first <= MyMax[startIndex].first) {
                    //first를 second으로 옮긴다.
                    MyMax[i].second = MyMax[i].first;
                    //그후 넣는다
                    MyMax[i].first = MyMax[startIndex].first + 1;
                }
                else if (MyMax[i].second <= MyMax[startIndex].first) MyMax[i].second = MyMax[startIndex].first + 1;
    
                if (!(MyMax[i].first == 0 && MyMax[i].second == 0))
                    maxValue = themax(themax(MyMax[i].first, 0) + themax(MyMax[i].second, 0), maxValue);
                else
                    maxValue = themax(themax(MyMax[i].first, 0) + themax(MyMax[i].second, 0) + 1, maxValue);
                break;
            }
        }
        return 0;
    }
    
    uint32_t FORTRESS_init() {
        freopen("input.txt", "r", stdin);
        ios::sync_with_stdio(false);
        uint32_t testCase;
        cin >> testCase;
        ++testCase;
        while (--testCase) {
            //initialization
    
            cin >> N;
            for (uint32_t i = 0; i < N; ++i)
                //한번도 할당받지않은경우 또는 자식이 없는 경우
                MyMax[i].first = MyMax[i].second = 0;
            maxValue = 0;
            //IsUsed.reset();
            //
    
            for (uint32_t i = 0; i < N; ++i) {
                cin >> MyTree[i].x >> MyTree[i].y >> MyTree[i].r;
            }
            sort(MyTree.begin(), MyTree.begin() + N, cmp);
            for (uint32_t i = 0; i < N - 1; ++i)
                FORTRESS_play(i);
    
            if (!(MyMax[N-1].first == 0 && MyMax[N - 1].second == 0))
                maxValue = themax(themax(MyMax[N - 1].first, 0) + themax(MyMax[N - 1].second, 0), maxValue);
            else
                maxValue = themax(themax(MyMax[N - 1].first, 0) + themax(MyMax[N - 1].second, 0) + 1, maxValue);
    
            cout << maxValue << endl;
        }
        return 0;
    }
    
    int main() {
        FORTRESS_init();
        return 0;
    }
    

    5년 전
2개의 댓글이 있습니다.
  • codeonwort
    codeonwort

    array<pair<uint32_t, uint32_t>, 101> MyMax;
    여기서 MyMax[i].first와 MyMax[i].second의 의미가 무엇인가요?


    5년 전 link
  • whatugonnado
    whatugonnado

    현재의 root가 가질 수 있는 1번째 최대크기와 2번째 최대 크기입니다.(root의 leaf가 2개이상일 수 있으므로)


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