글 읽기 - 출력 제한이 정상적이지 않은 것 같습니다.

jhhope1 5년 전 0

정상적인 출력문을 지우고 6글자의 string만 M번 출력해도 출력 초과가 납니다.

line 83의 dfs()함수에서 출력은 단 한 번 실행되는 것을 확인했습니다.

#include <bits/stdc++.h>
using namespace std;
int N, ck[100005], te,M;
pair<int, int>rtor[100005];
vector <int> cn[100005], cklist;
pair<int, int> cnt[100005];
void dfs_sort(int i){
    if(ck[i])return;
    ck[i]=1;
    if(i!=0&&cn[i].size()==2){
        if(ck[cn[i][1]])swap(cn[i][1], cn[i][0]);
        rtor[cn[i][1]].first=rtor[i].first=rtor[cn[i][0]].first;
        rtor[i].second=rtor[cn[i][0]].second+1;
        rtor[cn[i][1]].second=rtor[i].second+1;
        cnt[i]={rtor[cn[i][0]].first, rtor[i].second};
        dfs_sort(cn[i][1]);
    }
    else{
        for(int j=0 ;j<cn[i].size();j++)if(ck[cn[i][j]]==1)swap(cn[i][j], cn[i][0]);
        if(rtor[i].second==0){
            rtor[i].first=i;
            cnt[i]={rtor[cn[i][0]].first, 1};
        }
        else if(i!=0){
            cnt[i]={rtor[cn[i][0]].first, rtor[i].second};
        }
        for(int j=0 ;j<cn[i].size();j++)dfs_sort(cn[i][j]);
    }
    return;
}
void dfs(int m,int n){
    int temp1, temp2;
    temp1=rtor[m].first;
    temp2=rtor[n].first;
    ck[temp1]=ck[temp2]=1;
    cklist.push_back(temp1);
    cklist.push_back(temp2);
    if(temp1==temp2){
        if(rtor[m].second>rtor[n].second) cout<<n+1<<"\n";
        else cout<<m+1<<"\n";
        return;
    }
    while(1){
        temp1 = cnt[temp1].first;
        if(ck[temp1]==1){
            cout<<n+1<<"\n";
            return;
        }
        ck[temp1]=1;
        cklist.push_back(temp1);
        if(temp1==0)break;
    }
    while(1){
        temp2=cnt[temp2].first;
        if(temp2==rtor[m].first){
            cout<<m+1<<"\n";
            return;}
        if(ck[temp2]==1){
            cout<<temp2+1<<"\n";
            return;
        }
        ck[temp2]=1;
        cklist.push_back(temp2);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>N;
    int temp1,temp2;
    for(int i = 0 ; i<N-1 ; i++){
        cin>>temp1>>temp2;
        cn[temp1-1].push_back(temp2-1);
        cn[temp2-1].push_back(temp1-1);
    }
    dfs_sort(0);
    cin>>M;
    for(int i = 0 ; i<N ; i++){
        ck[i]=0;
    }
    for(int i=0 ; i<M ; i++){
        cin>>temp1>>temp2;
        //dfs(temp1-1,temp2-1);
        puts("YAYYAY");
        for(int x:cklist)ck[x]=0;
        cklist.clear();
    }
}

djm03178 5년 전 0

출력 초과는 어떤 절대적인 기준이 정해져 있는 것이 아니라 "올바른 출력"에 비해 너무 많은 출력이 발생할 때 받게 됩니다. 만일 1을 M줄 출력하는 게 정답인 케이스가 있다면, 6글자씩 M줄을 출력하는 건 너무 많죠.

jh05013 5년 전 0

https://www.acmicpc.net/help/j...

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

문제

문제

출처

ICPC

출력 제한이 정상적이지 않은 것 같습니다.

jhhope1 5년 전 0

djm03178 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말