글 읽기 - 반례가 있을까요..?

herdson 4년 전 0

50% 쯤에서 터져버리는데 도대체 어떤 것을 고려해야 되는지 감도 안잡히네요 후...

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int amatrix[500][500] {};

void tsort(int total, vector<int> &degree);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int n;
    cin >> n;
    while (n--)
    {
        memset(amatrix, 0, sizeof amatrix);
        int teams;
        cin >> teams;
       
        vector<int> ranking(teams, 0);
        vector<int> indegree(teams, 0);
       
        for (int i = 0; i < teams; ++i)
            cin >> ranking[i];
           
        for (int j = 0; j < teams; ++j)
        {
            for (int k = j + 1; k < teams; ++k)
            {
                amatrix[ranking[j] - 1][ranking[k] - 1] = 1;
                ++indegree[ranking[k] - 1];
            }
        }
        
        int changes;
        cin >> changes;
        while (changes--)
        {
            int hijacked, busted;
            cin >> hijacked >> busted;
            if (indegree[hijacked - 1] > 0)
            {
                --indegree[hijacked - 1];
            }
            ++indegree[busted - 1];
            amatrix[busted - 1][hijacked - 1] = 0;
            amatrix[hijacked - 1][busted - 1] = 1;
        }
        
        tsort(teams, indegree);
    }
}

void tsort(int total, vector<int> &degree)
{
    queue<int> search;
    queue<int> complete;
   
    for (int i = 0; i < total; ++i)
    {
        if (!degree[i])
            search.push(i + 1);
    }
   
    while (!search.empty())
    {
        if (search.size() > 1)
        {
            cout << "?\n";
            return;
        }
       
        int target(search.front());
        search.pop(); complete.push(target);
        for (int x = 0; x < total; ++x)
        {
            if (amatrix[target - 1][x])
            {
                --degree[x];
                if (!degree[x])
                    search.push(x + 1);
            }
        }
    }
   
    if (complete.size() != total)
    {
        cout << "IMPOSSIBLE\n";
    }
    else
    {
        while (!complete.empty())
        {
            cout << complete.front() << " ";
            complete.pop();
        }
        cout << "\n";
    }
} 

yehyun 4년 전 5

반례입니다.

input
1
3
1 3 2
1
1 3

answer
3 1 2

herdson 4년 전 0

제가 찾다찾다 너무 이해가 안되는게 있는데

이 케이스의 아웃풋이 왜

2 1

이렇게 나와야 되는건가요;;;?

1번이 1등이고 2번이 2등인 상황에서 1번이 2번을 다시 이겼을 뿐인데 왜 답은 2 1 이 되어야 하는건지 혼란 그 자체네요 지금...

herdson 4년 전 0

ㄴ다시 읽어보니 등수가 상대적인게 아니라 그저 바뀌었을 뿐이었군요...

다시 천천히 읽고 풀어봐야겠습니다.

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

문제

문제

출처

ICPC

반례가 있을까요..?

herdson 4년 전 0

yehyun 4년 전 5

herdson 4년 전 0

herdson 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말