글 읽기 - 반례를 못찾겠습니다.

purpose 4년 전 0

처음에는 그냥 오름차순으로 진행하면 된다고 생각해서 진행했는데

2-2를 읽어보니 그게 아니라서

이런 경우를 처리해주기 위해서

42 ~ 44번 행을 통해서 a[1][0]과 a[1][1]을 뒤집어서 3에 먼저 접근한 후에 2에 접근할 수 있도록 해주었습니다.

그 결과 예제와 제가 돌려본 반례들은 맞는데 어떤 경우에 정답이 안나오는지 모르겠습니다.

제가 뭘 놓치고 있는지 알려주시면 정말 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector <int> a[100001]; // codeforce에서 컴파일하면 여기서 런타임에러가 발생.
    vector <int> v;
    queue <int> q;
    bool check[100001] = { 0, };
    int n;
    cin >> n;

    for(int i = 0; i < n-1; ++i){
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        v.push_back(a);
    }
    if(v[0] != 1){
        cout << 0;
        return 0;
    }

    q.push(1);
    int index = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();

        if(v[index+1] < v[index] && a[x].size() == 2){
            reverse(a[x].begin(), a[x].end());
        }
        for(int i = 0; i < a[x].size(); ++i){
            if(v[index] == a[x][i] && check[v[index]] == false){
                q.push(v[index]); // 입력된 순서랑 같은 경우에만 큐에 추가해서 다음 과정 진행.
                check[v[index]] = true;
                index++;
            }else
                continue;
        }

    }

    //전 과정을 입력된 순서와 같게 진행할 수 있다면 index가 n과 같은 값을 나타내고 있을 것.
    if(index == n)
        cout << 1;
    else
        cout << 0;

	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

purpose 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말