글 읽기 - 좀비 문제 Input이 잘못된 것 같습니다

se3256_song 7년 전 0

별짓을 다해봐도 시간초과가 나오길래

실제 최대유량 구하는 flow 부분에 내용 다 빼고 return 0만 넣어서

즉 Input만 받게 만들었는데도 틀렸습니다가 아닌 시간 초과가 나오네요

Input이 예제처럼 들어오는게 아니라 입력값이 부족하여

대기하다가 시간초과가 나오는 것으로 보입니다

확인 부탁드립니다

import java.util.*;
import java.io.*;

public class Main {
	static int T, N, start, end, G, S, HN, L, Answer, step;
	static int [] H;
	static int index;
	static ArrayList<ArrayList<int []>> line;
	static int INF=1000000;
	static int [] visit;
	static int [] parents;
	static int [] check;
	static Queue<Integer> Q;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		T = sc.nextInt();
		
		for(int test_case=1; test_case<=T; test_case++){
			N = sc.nextInt();
			start = sc.nextInt();
			G = sc.nextInt();
			S = sc.nextInt();
			HN = sc.nextInt();
			
			H = new int [HN];
			end = (S+1)*(S+1)*(N-1)*N+HN+1;
			line = new ArrayList<ArrayList<int []>>();
			for(int i=0; i<=end; i++){
				line.add(new ArrayList<int []>());
			}
			
			for(int i=0; i<HN; i++){
				int tmp = sc.nextInt();
				add_edge((tmp-1)*(S+1)+1+S, end, INF, 0);
			}
			
			L = sc.nextInt();
			
			for(int i=1; i<=L; i++){
				int a = sc.nextInt();
				int b = sc.nextInt();
				int c = sc.nextInt();
				int d = sc.nextInt();
				
				add_edge((a-1)*(S+1)+1,(b-1)*(S+1)+1+d,c, S-d);
			}
			
			for(int i=1; i<=N; i++){
				for(int j=0; j<S; j++){
					add_edge((i-1)*(S+1)+1+j, (i-1)*(S+1)+2+j, INF, 0);
				}
			}
			
			add_edge(0, (start-1)*(S+1)+1, G, 0);
			
			Q = new LinkedList<Integer>();
			visit = new int [end+1];
			parents = new int [end+1];
			check = new int [end+1];
			start = 0;
			step = 0;
			
			Answer = flow();
			
			bw.write(Answer+"\n");
		}
		bw.close();
	}
	
	public static int flow(){
		int ans = 0;
		while(true){
			step++;
			Q.clear();
			Q.add(start);
			visit[start]=step;
			boolean cnt = false;
			
			while(!Q.isEmpty() && cnt==false){
				int x = Q.poll();
				for(int i=0; i<line.get(x).size(); i++){
					int next = line.get(x).get(i)[0];
					if(line.get(x).get(i)[1]-line.get(x).get(i)[2]>0 && visit[next]!=step){
						visit[next]=step;
						parents[next]=x;
						check[next]=i;
						Q.add(next);
						if(next==end){
							cnt = true;
							break;
						}
					}
				}
			}
			
			if(visit[end]!=step) break;
			
			int flow = INF;
			for(int j=end; j!=0; j=parents[j]){
				flow = Math.min(flow, line.get(parents[j]).get(check[j])[1]-line.get(parents[j]).get(check[j])[2]);
			}
			
			for(int j=end; j!=0; j=parents[j]){
				line.get(parents[j]).get(check[j])[2]+=flow;
				line.get(j).get(line.get(parents[j]).get(check[j])[3])[2]-=flow;
			}
			ans += flow;
		}
		return ans;
	}
	
	public static void add_edge(int x, int y, int c, int t){
		for(int i=0; i<=t; i++){
			line.get(x+i).add(new int [] {y+i,c,0,line.get(y).size()});
			line.get(y+i).add(new int [] {x+i,0,0,line.get(x).size()-1});
		}
	}
}

isku 7년 전 0

주어준 코드에서 시간초과에 대한 분석은 해보지는 않았지만

질문하신 입력에 대한 부분은

아래와 같이 제가 실행해본 결과 틀렸습니다를 받았습니다.

아마 입력 테스트 해보실 때 출력을 안해주셔서 그런 것 아닐까 싶습니다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner input = new Scanner(System.in);

		int testCase = input.nextInt();
		while (testCase-- > 0) {
			int n = input.nextInt();

			int i = input.nextInt();
			int g = input.nextInt();
			int s = input.nextInt();

			int m = input.nextInt();
			for (int j = 0; j < m; j++) {
				int ok = input.nextInt();
			}

			int r = input.nextInt();
			for (int j = 0; j < r; j++) {
				int a = input.nextInt();
				int b = input.nextInt();
				int p = input.nextInt();
				int t = input.nextInt();
			}

			System.out.println(1);
		}
	}
}

se3256_song 7년 전 0

출력은 위에 소스에서 보이는 것처럼 BufferedWriter 로 출력하여 없지 않구요

edge추가에 배열 생성에 다 빼버리니까

틀렸습니다가 나오네요

결국 연산은 커녕 기본적인 edge랑 ArrayList, 배열만 만들다가 시간초과가 나온다는 건데....

edge랑 만드는 건 교육 받을 때 교재에 나온대로 만든건데...좀 황당하네요

import java.util.*;
import java.io.*;

public class Main {
	static int T, N, start, end, G, S, HN, L, Answer, step;
	static int [] H;
	static int index;
	static ArrayList<ArrayList<int []>> line;
	static int INF=1000000;
	static int [] visit;
	static int [] parents;
	static int [] check;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		
		for(int test_case=1; test_case<=T; test_case++){
			N = sc.nextInt();
			start = sc.nextInt();
			G = sc.nextInt();
			S = sc.nextInt();
			HN = sc.nextInt();
			
			H = new int [HN];
			end = (S+1)*(S+1)*(N-1)*N+HN+1;
			line = new ArrayList<ArrayList<int []>>();
			for(int i=0; i<=0; i++){
				line.add(new ArrayList<int []>());
			}
			
			for(int i=0; i<HN; i++){
				int tmp = sc.nextInt();
				//add_edge((tmp-1)*(S+1)+1+S, end, INF, 0);
			}
			
			L = sc.nextInt();
			
			for(int i=1; i<=L; i++){
				int a = sc.nextInt();
				int b = sc.nextInt();
				int c = sc.nextInt();
				int d = sc.nextInt();
				
				//add_edge((a-1)*(S+1)+1,(b-1)*(S+1)+1+d,c, S-d);
			}
			
			for(int i=1; i<=N; i++){
				for(int j=0; j<S; j++){
					//add_edge((i-1)*(S+1)+1+j, (i-1)*(S+1)+2+j, INF, 0);
				}
			}
			
			//add_edge(0, (start-1)*(S+1)+1, G, 0);
			
			//visit = new int [end+1];
			//parents = new int [end+1];
			//check = new int [end+1];
			//start = 0;
			//step = 0;
			
			Answer = flow();
			
			System.out.println(Answer);
		}
	}
	
	public static int flow(){
		return 0;
	}
	
	public static void add_edge(int x, int y, int c, int t){
		for(int i=0; i<=t; i++){
			line.get(x+i).add(new int [] {y+i,c,0,line.get(y).size()});
			line.get(y+i).add(new int [] {x+i,0,0,line.get(x).size()-1});
		}
	}
}

se3256_song 7년 전 0

제가 뭔 생각을 했던건지....

sink 를 너무 크게 잡았네요

그로 인해 ArrayList든 배열이든 쓸데없이 너무 크게 잡히면서

아마 힙메모리 초과가 나온것 같습니다

잘 수정해서 겨우 풀었네요 ㅠ.ㅠ

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

문제

문제

출처

ICPC

좀비 문제 Input이 잘못된 것 같습니다

se3256_song 7년 전 0

isku 7년 전 0

se3256_song 7년 전 0

se3256_song 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말