글 읽기 - 어디가 틀렸을까요? 반례있을까요?

safkddlfks 4년 전 0

후위순회, 레이즈, 세그먼트트리를 이용하여 작성했습니다!

예제는 잘 돌아갑니다. 또한, 테스트로 만든 예제 역시 잘돌아갑니다.

채점 시, '틀렸습니다'가 나옵니다.

코드 작성 중 오류나, 반례가 있을까요?

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class P15782_1 {
	
	static ArrayList<Integer> [] list;
	static boolean check[] = new boolean[100001];
	static int numChild[] = new int[100001];
	static int numbering[] = new int[100001];
	static int p[] = new int[100001];
	static int a[];
	static int cnt;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());
		
		int h = (int)Math.ceil(Math.log(N)/Math.log(2));
		int tree_size = (int)Math.pow(2, h+1);
		int lazy[]  = new int[tree_size]; // lazy 배열
		int tree[] = new int[tree_size]; // tree 배열
		a= new int[N+1]; // 가중치 배열
		list = new ArrayList[N+1]; //간선 정보 배열
		
		
		//간선 정보 입력 시작.
		for(int i = 0; i<=N; i++){
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < N - 1; i++) {
			token = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(token.nextToken());
			int y = Integer.parseInt(token.nextToken());
			list[x].add(y);
		}
		
		
		//간선 정보 입력 끝
		//가중치 입력 시작.
		token = new StringTokenizer(br.readLine());
		for(int i = 1; i<=N; i++){
			a[i] = Integer.parseInt(token.nextToken());
		}
		//가중치 입력 끝
		init_data(1);
		
		init_tree(tree, 1, 1, N);
		
		
		for(int i = 0; i<M; i++){
			token = new StringTokenizer(br.readLine());
			int aa= Integer.parseInt(token.nextToken());
			int b = Integer.parseInt(token.nextToken());
			
			if(aa == 1){
				System.out.println(xor(tree, lazy, 1,1,N,numbering[b]-numChild[b], numbering[b]));
				continue;
			}
			if(aa == 2){
				int c = Integer.parseInt(token.nextToken());	
				update_range(tree,lazy,1,1,N,numbering[b]-numChild[b], numbering[b],c);
				continue;
			}
		}
		
	}

	public static int init_data(int current){
		
		check[current] = true;
		
		int child = 0;
		
		for(int next : list[current]){
			if(!check[next]){
				child += init_data(next);
			}
		}
		
		numbering[current] = ++cnt;
		p[cnt] = a[current];
		numChild[current] = child;
		
		return child + 1;
	}
	
	public static void init_tree(int tree[], int node, int start, int end){
		if(start == end){
			tree[node] = p[start];
		}
		
		else{
			init_tree(tree, node*2, start, (start+end)/2);
			init_tree(tree, node*2+1, (start+end)/2+1,end);
			tree[node] = tree[node*2]^tree[node*2+1];
		}
	}
	
	public static long xor(int tree[], int lazy[], int node, int start, int end, int left, int right){
		
		update_lazy(tree, lazy, node, start, end);
		
		if(left>end || right < start) return 0;
		
		if(left <= start && end <=right) return tree[node];
		
		return xor(tree, lazy, node*2, start, (start+end)/2, left, right) ^
				xor(tree, lazy, node*2+1, (start+end)/2+1, end, left, right);
	}
	
	public static void update_lazy(int tree[], int lazy[], int node, int start, int end){
		if(lazy[node] != 0){ //lazy 값이 있으면,
			if(start == end) tree[node] ^= lazy[node];
			
			if(start != end){
				lazy[node*2] ^= lazy[node];
				lazy[node*2+1] ^= lazy[node];
			}
			lazy[node] = 0; //lazy값을 update다 했다면, 0으로 초기화.
		}
	}
	
	public static void update_range(int tree[], int lazy[], int node, int start, int end, int left, int right, int diff){
		
		update_lazy(tree, lazy, node, start, end);
		
		if(left > end  || start > right) return;
		if(left <= start && right >= end){
			if(start == end) tree[node] ^= diff;
			if(start != end){ //자식 노드가 있으면, 자식노드 lazy에도 변경값을 xor 해준다.
				lazy[node*2] ^= diff;
				lazy[node*2+1] ^= diff;
			}
			return;
		}
		
		//왼쪽 노드, 오른쪽 노드를 호출 update 계속 해준다.
		update_range(tree, lazy, node * 2, start, (start+end)/2, left, right, diff);
		update_range(tree, lazy, node * 2 +1, (start+end)/2+1, end, left, right, diff);
		tree[node] = tree[node*2] ^ tree[node*2+1];
	}
}

isku 4년 전 0

안녕하세요.

정답을 맞으셨길래 코드를 봤더니 제 코드여서 깜놀했네요 ㄷㄷ;

github에 공개된 소스는 잘 정리되지 않은 소스인데 ㅜㅜ 부끄

tree를 구축할 때 아마 양방향이 아니여서 틀린걸로 예상됩니다!

다른 부분은 안 보고, 컴파일도 안해봤습니다 :D

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

문제

문제

출처

ICPC

어디가 틀렸을까요? 반례있을까요?

safkddlfks 4년 전 0

isku 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말