글 읽기 - [assert() 사용] 틀린 채점 데이터가 있습니다.

slah007 4년 전 4

graph의 connected component의 수 A, 문제의 정답 B라 했을 때

edge를 추가해서 connected이고 Euler path가 존재하는 graph를 얻어야 하므로 B>=A-1이어야 합니다. (연결되려면 한 edge는 필요하므로)

하지만, 아래 코드를 통해 적당한 답 B = (sum>2?sum/2-1:0)와 connected component의 수 A = odd.size()를 구해서 B를 정답으로 제출했을 때,

1. 채점이 80% 이상 진행되고 (즉, 80% 이하의 채점에 대해 B가 맞는 답이고)

2. assert(B>=A-1)를 추가하면 약 50% 부근에서 "런타임 에러"를 받습니다.

만약 어느 TC에서 틀렸는지를 보실 수 있는 분이라면, 1, 2번의 사실은 채점 번호 18965946, 18966004를 차례로 보시면 명확합니다.

아래에 assert()로 RTE를 받은 코드를 첨부합니다. 만약 제가 문제를 잘못 이해했거나, 아래 코드에서 dfs 함수인 go()가 틀린 것 같다면 이 글은 무시해주세요.

#include <bits/stdc++.h>
using namespace std;

const int LM = 1004;

int V, E;
int deg[LM];
vector<int>adj[LM];
bitset<LM> chk;

int go(int v){
    chk[v] = true;
    int result = deg[v]%2;
    for(int i=0;i<(int)adj[v].size();i++){
        int next = adj[v][i];
        if(chk[next]) continue;
        result += go(next);
    }
    return result;
}

int main(){
    scanf("%d%d",&V,&E);
    while(E--){
        int a,b;
        scanf("%d%d",&a,&b);
        deg[a]++;
        deg[b]++;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    priority_queue<int> odd; ///connected component의 odd degree vertex 수
    int sum = 0;
    for(int i=1;i<=V;i++)if(!chk[i]){
        int tmp = go(i);
        odd.push(tmp);
        sum += tmp;
    }

    /*int ans = 0;
    while(odd.size()>=2){
        int o1 = odd.top(); odd.pop();
        int o2 = odd.top(); odd.pop();
        assert(o1%2==0 && o2%2==0);
        int o = 0;
        if(o1>0 && o2>0) o = o1+o2-2;
        else if(o1>0 && o2==0) o = o1+o2;
        else if(o1==0 && o2==0) o = 2;
        ans++;
        odd.push(o);
    }
    if(odd.top()>2) ans += odd.top()/2 - 1;
    printf("%d\n", ans);*/
    assert((sum>2?sum/2-1:0)>=odd.size()-1);
    printf("%d\n", sum>2?sum/2-1:0);
    return 0;
}

koosaga 4년 전 1

저의 정답 코드를 열어봤고, "5 0" 이라는 입력에서 잘못된 답을 내놓습니다 (0개 추가). 원래 올바른 답을 내놓는 걸로 구현했다가 틀린 버전으로 바꿔서 맞았네요. 수정하는 것이 맞다고 생각합니다.

jyon 3년 전 0

작성하신 코드와 같은 방법으로 구현했는데요, 짝수점 하나로만 구성된 component는 연결하지 않아야만 accept되는 걸 확인했습니다. (채점번호 23735711)

startlink 3년 전 1

재채점했습니다.

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

문제

문제

출처

ICPC

[assert() 사용] 틀린 채점 데이터가 있습니다.

slah007 4년 전 4

koosaga 4년 전 1

jyon 3년 전 0

startlink 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말