EDITORWARS 질문드립니다.

  • KIMMUSIC
    KIMMUSIC

    groupe[x][0] 으로 x의 적을 관리 했습니다 웬만한 예제들 생각해서 다 넣어봤을때는 잘 나왔는데 오답으로 뜨네요 어디가 틀린건지 알수 있을까요..

    #include <iostream>
    #include <vector>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    
    vector<int> parent;
    vector<int> Rank;
    int groupe[10001][1];
    
    int Find(int x)
    {
        if (x == -1)
        {
            return -1;
        }
        if (x == parent[x])
        {
            return x;
        }
        else
        {
            return parent[x] = Find(parent[x]);
        }
    }
    
    void merge(int x, int y)
    {
        x = Find(x);
        y = Find(y);
    
        if (x == y)
        {
            return;
        }
    
        if (Rank[x] > Rank[y]) swap(x, y);
    
        parent[x] = y;
        if (groupe[x][0] != -1 && groupe[y][0] != -1)
        {
            merge(groupe[x][0], groupe[y][0]);
        }
        if(groupe[x][0] == -1)
            groupe[x][0] = groupe[y][0];
        if (groupe[y][0] == -1)
            groupe[y][0] = groupe[x][0];
    
        if (Rank[x] == Rank[y]) Rank[y]++;
    }
    
    int main(void)
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
    
        int testN;
        cin >> testN;
        while (testN--)
        {
            int N, M;
            int res = 0;
            int visited2[10001] = { 0, };
            int resv[10001] = { 0, };
            int flag = 0;
            memset(groupe, -1, sizeof(groupe));
            cin >> N >> M;
            parent.clear();
            Rank.clear();
            parent.resize(N);
    
            for (int i = 0; i < N; ++i)
            {
                parent[i] = i;
            }
    
            Rank.resize(N);
    
            for (int i = 1; i <= M; ++i)
            {
                string VOE;
                int a, b;
    
                cin >> VOE >> a >> b;
    
                if (VOE == "ACK")
                {
    
                    if (Find(groupe[Find(a)][0]) == Find(b) || Find(groupe[Find(b)][0]) == Find(a))
                    {
                        cout << "CONTRADICTION AT " << i << endl;
                        flag = 1;
                        continue;
                    }
    
    
                    merge(a, b);
                }
    
    
    
                if(VOE == "DIS")
                {
                int Pa = Find(a);
                int Pb = Find(b);
    
                    if (Pa == Pb)
                    {
                        cout << "CONTRADICTION AT " << i << endl;
                        flag = 1;
                        continue;
                    }
    
                    if (groupe[Pa][0] == -1)
                        groupe[Pa][0] = Pb;
    
                    else
                    {
                        merge(groupe[Pa][0], Pb);
                    }
    
                    if (groupe[Pb][0] == -1)
                    {
                        groupe[Pb][0] = a;
                    }
                    else
                    {
                        merge(groupe[Pb][0], Pa);
                    }
                }
            }
    
            for (int i = 0; i < N; ++i)
            {
                resv[Find(i)]++;
            }
    
                for (int i = 0; i < N; ++i)
                {
                    int k = Find(i);
                    if (!visited2[k])
                    {
                        visited2[k] = 1;
                        if (groupe[k][0] != -1) {
    
                            res += max(resv[k], resv[Find(groupe[k][0])]);
                            visited2[k] = visited2[Find(groupe[k][0])] = 1;
                        }
    
                        else
                        {
                            res += resv[k];
                        }
    
                    }
    
                }
                if(flag != 1)
                    cout <<"MAX PARTY SIZE IS " << res << endl;
        }
    }
    

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