글 읽기 - 도와주세요..

rkdalsdn7 2년 전 0

예제는 나오는데 6%에서 틀립니다

이것저것 해봤는데 반례만들기도 쉽지 않네요

#include <bits/stdc++.h>
using namespace std;

int n,m,o,x,w,cnt;
// d - input, 각 노드의 자식들을 저장
// num - dfs로 바꾼 노드번호를 저장
// r - r[i] = x => 루트가 i인 서브트리에서 가장 번호가 큰 노드가 x
vector<vector<int> > d;
vector<int> num,r,tree,lazy;
void dfs(int,int);
void propagate(int,int,int);
void query(int,int,int,int,int,int);
void find(int,int,int,int);

int main() {
	scanf("%d%d",&n,&m);
	d.resize(n+2);
	num.resize(n+2);
	r.resize(n+2);
	tree.resize(4*n);
	lazy.resize(4*n);
	for(int i=1; i<=n; i++) r[i] = i;
	
	for(int i=1; i<=n; i++){
		scanf("%d",&x);
		if(x!=-1) d[x].push_back(i);
	}
	
	dfs(0,1);
	
	for(int i=0; i<m; i++){
		scanf("%d%d",&o,&x);
		if(o==1){
			scanf("%d",&w);
			query(num[x],r[num[x]],w,1,1,n);
		}
		else find(num[x],1,1,n);
	}
}

void dfs(int prev,int cur){
	r[prev] = ++cnt;
	num[cur] = cnt;
	for(int next : d[cur]) dfs(num[cur],next);
}

void propagate(int node,int l ,int r){
	if(lazy[node]!=0){
		if(l!=r){
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		tree[node] += lazy[node];
		lazy[node] = 0;
	}
}

void query(int l, int r, int val, int node, int start, int end){
	propagate(node,start,end);
	
	if(r<start || end<l) return;
	if(l<=start && end<=r){
		lazy[node] += val;
		propagate(node,start,end);
		return;
	}
	
	int mid = (start+end)/2;
	query(l,r,val,node*2,start,mid);
	query(l,r,val,node*2+1,mid+1,end);
}

void find(int i, int node, int start, int end){
	propagate(node,start,end);
	
	if(i<start || end<i) return;
	if(start==end){
		printf("%d\n",tree[node]);
		return;
	}
	
	int mid = (start+end)/2;
	find(i,node*2,start,mid);
	find(i,node*2+1,mid+1,end);
}

rkdalsdn7 2년 전 0

dfs 함수에서 오류가 있었네요

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

문제

문제

출처

ICPC

도와주세요..

rkdalsdn7 2년 전 0

rkdalsdn7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말