글 읽기 - 2820 질문드려요~

algospot 8년 전 0

아주 1차원적으로 시간초과뜰 거 알면서 짜긴했는데..

짜다가 union_find 할까 생각해보니, 각 자식들이 최고 높은 상사를 가리키게 해서는 오류를 범해서 그것도 아닌거같고

시간초과를 어떻게 면할수있을까요?

#include <iostream>
#include <vector>
using namespace std;
struct G {
	int money;
	vector<int> child;
};
G g[500050];
int N,M,S;
void dfs(int p, int m) {
	int i,j;
	for(i=0;i<g[p].child.size();i++) {
		g[g[p].child[i]].money+=m;
		dfs(g[p].child[i],m);
	}
}
int main(void) {
	int i,j,k,a,b;
	char order;
	cin>>N>>M;
	cin>>S;
	g[1].money=S;
	for(i=2;i<=N;i++) {
		cin>>a>>b;
		g[i].money=a;
		g[b].child.push_back(i);
	}
	//query
	for(i=0;i<M;i++) {
		cin>>order;
		if(order=='p') {
			cin>>a>>b;
			dfs(a,b);	
		} else if(order=='u') {
			cin>>a;
			cout<<g[a].money<<endl;
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

2820 질문드려요~

algospot 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말