글 읽기 - 3일째 고민중입니다. ㅜㅜ 도와주세요!!!

keh0711 6년 전 0

타임에러가 뜹니다. 무엇이 잘못되었는지.... 도통 실마리가 안잡힙니다.

일단 예시는 문제없이 답이 나오는데...4% 채점중에서 타임에러가 뜨니...

4%로 정도면 데이터파일의 양도 적을텐데...

어디가 문제인지... 이렇게 scanf()로 받는 부분에서 엔터값을 기다리다가 멈추어서 타임에러가 나는건 아닌지...

별 생각을 다합니다.

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

#define INF 9999999

int p[100001], eclr[100001], n;

int f(int a, int b) //접점을 찾는 함수
{
    if(a==b)
        return a;
    vector<int> v;
    v.push_back(a);
    while(a!=0){
        a=p[a];
        v.push_back(a);
    }
    while(true){
        for(int i=0;i<v.size();i++)
            if(b==v[i]){
                v.clear();
                return b;
            }
        b=p[b];
    }
    return -1;
}


int main(int argc, const char * argv[]) {
    vector<int>v;
    int q, k, n1, n2, clr;
    scanf("%d%d", &n, &q);
    
    for(int i=0;i<q;i++)
    {
        scanf(" %d%d%d", &k, &n1, &n2);
        if(k==1){  //paint
            scanf("%d",&clr);
            //cin>>clr;
            int pt=f(n1, n2);
            while(pt!=n1){
                eclr[n1]=clr;
                n1=p[n1];
            }
            while(pt!=n2){
                eclr[n2]=clr;
                n2=p[n2];
            }
        }
        else if(k==2) //move
            p[n1]=n2;
        else //count
        {
            if(n1==n2){
                cout<<0<<endl;
            }
            else{
                int pt=f(n1, n2), sum=1;
                while(pt!=n1){
                    v.push_back(eclr[n1]);
                    n1=p[n1];
                }
                while(pt!=n2){
                    v.push_back(eclr[n2]);
                    n2=p[n2];
                }
                sort(v.begin(), v.end());
                for(int i=1;i<v.size();i++)
                {
                    if(v[i-1]!=v[i])
                        sum++;
                }
                cout<<sum<<endl;
            }
            v.clear();
        }
    }
    return 0;
}

onjo0127 6년 전 1

BOJ는 신속한 채점을 위해서 데이터량이 더 많은 테스트케이스부터 채점하는 걸로 알고 있습니다..

4%에서 시간초과가 난다면 알고리즘이 느리기 때문일 가능성이 높습니다.

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

문제

문제

출처

ICPC

3일째 고민중입니다. ㅜㅜ 도와주세요!!!

keh0711 6년 전 0

onjo0127 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말