글 읽기 - 시간 초과가 나요ㅜㅜ

tw99534 7년 전 0

계속 시간 초과가 나네요ㅜㅜ 도대체 어디 부분이 문제일까요....??

import java.util.Scanner;
import java.util.LinkedList;
public class Main {
	int[] boss= new int[500001];	
	int[] payment= new int[500001];
	int N;	
	Main(int N){
		this.N=N;
	}
	void ud(int bossNum,int add){
		int qxS;
		LinkedList<Integer> qx = new LinkedList<Integer>();
		qx.add(bossNum);	
		while(!qx.isEmpty()){
			qxS=qx.size();
			for(int i=0;i<qxS;i++){
				int px= qx.getFirst();
				qx.remove();
				for(int j=1;j<=N;j++){
					if(boss[j] == px){
						payment[j]+=add;
						qx.add(j);
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		LinkedList<Integer> result= new LinkedList<Integer>();
		int a=0,b=0;
		String[] ud={""};
		ud=sc.nextLine().split(" ");
		int N = Integer.parseInt(ud[0]);
		int M = Integer.parseInt(ud[1]);
		Main m = new Main(N);	
		
		//보스배열, 월급 배열
		for(int i =1;i<=N;i++){	
			ud=sc.nextLine().split(" ");
			if(i==1){
				m.boss[1]=0;
				m.payment[i]=Integer.parseInt(ud[0]);
				continue;
			}else{
				m.boss[i]=Integer.parseInt(ud[1]);
				m.payment[i]=Integer.parseInt(ud[0]);	
			}
		} 
		
		for(int i=0;i<M;i++){
			ud=sc.nextLine().split(" ");
			char temp= ud[0].charAt(0);
			if(temp =='p'){
				a= Integer.parseInt(ud[1]); //보스
				b= Integer.parseInt(ud[2]); // 페이
				m.ud(a,b);
			}else if(temp=='u'){
				a= Integer.parseInt(ud[1]);
				result.add(m.payment[a]);
			}
		}
		
		while(!result.isEmpty()){
			System.out.println(result.removeFirst());
		}
		
	}
}

portableangel 7년 전 0

직접 업데이트와 계산을 쿼리마다 처리하게 되면 연산량이 500000*500000으로 제한시간 내에 수행될 수 없습니다.

풀이 방법은 많을 수 있겠지만,

저는 DFS를 이용해 트리를 펼치고, 펼쳐 놓은 트리를 리프로 하는 세그먼트 트리를 만들어 lazy propagation을 이용해 풀었습니다.

간신히 1초 안쪽으로 도네요.

해당 알고리즘에 관심이 있으시다면 segment tree, lazy propagation 등의 키워드로 검색해보세요.

tw99534 7년 전 0

아 그렇군요 생각보다 복잡해 지네요...ㅜㅜ 세그먼트 트리를 공부해봐야 겠습니다. 조언 정말 감사드립니다!

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

문제

문제

출처

ICPC

시간 초과가 나요ㅜㅜ

tw99534 7년 전 0

portableangel 7년 전 0

tw99534 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말