글 읽기 - HLD 처음 짜봅니다

wnguscjf01 2년 전 0

틀리는 테스트 케이스 알려주실 수 있을까요?

#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
int wei[MAXN], cor[MAXN], dfs[MAXN], hv[MAXN], dep[MAXN], n;
vector<pair<int,pair<int,int> > > v[MAXN];
pair<int,pair<int,int> > parn[MAXN];
int f1(int p, pair<int,pair<int,int> > par, int de){
	int i, w=1;
	parn[p] = par;
	dep[p] = de;
	for(i=0; i<v[p].size(); i++){
		if(v[p][i].first == par.first) continue;
		f1(v[p][i].first, {p,v[p][i].second}, de+1);
		w += wei[v[p][i].first];
		cor[v[p][i].second.second] = v[p][i].first;
	}
	wei[p] = w;
	pair<int,pair<int,int> > tmp;
	for(i=1; i<v[p].size(); i++){
		if(v[p][i].first == par.first) continue;
		if(v[p][0].first==par.first || wei[v[p][i].first] > wei[v[p][0].first]){
			tmp=v[p][i]; v[p][i]=v[p][0]; v[p][0]=tmp;
		}
	}
	return 0;
}
int tree[4*MAXN], k, cnt;
int mark(int p, int par){
	int i;
	dfs[p] = ++cnt;
	for(i=0; i<v[p].size(); i++){
		if(v[p][i].first == par) continue;
		if(i==0) hv[v[p][i].first] = hv[p];
		else hv[v[p][i].first] = v[p][i].first;
	}
	for(i=0; i<v[p].size(); i++){
		if(v[p][i].first == par) continue;
		mark(v[p][i].first, p);
	}
	return 0;
}
int ftree(int a, int b){
	if(a>b){
		int tmp=a; a=b; b=tmp;
	}
	int l=k+a, r=k-1+b, maxi=0;
	while(l<=r){
		if(l%2==1){
			maxi = max(maxi, tree[l]);
			l++;
		}
		if(r%2==0){
			maxi = max(maxi, tree[r]);
			r--;
		}
		l/=2; r/=2;
	}
	return maxi;
}
int main()
{
	int q, i, j;
	cin >> n;
	for(i=1; i<=n-1; i++){
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		v[a].push_back({b,{c,i}});
		v[b].push_back({a,{c,i}});
	}
	f1(1,{-1,{-1,-1}},1);
	hv[1] = 1;	
	mark(1,-1);
	k=1;
	while(k<n) k*=2;
	for(i=2; i<=n; i++) tree[k-1+dfs[i]] = parn[i].second.first;
	for(i=n-1; i>=1; i--) tree[i] = max(tree[i*2], tree[i*2+1]);
	cin >> q;
	for(i=1; i<=q; i++){
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		if(a==1){
			int l = k-1+dfs[cor[b]];
			tree[l] = c;
			for(l=l/2; l>=1; l/=2) tree[l] = max(tree[l*2],tree[l*2+1]);
		}
		else{
			int maxi =0;
			while(hv[c]!=hv[b]){
				if(dep[hv[b]] > dep[hv[c]]){
					int tmp=c; c=b; b=tmp;
				}
				if(c!=hv[c]){
					maxi = max(maxi, ftree(dfs[c],dfs[hv[c]]));
					c = hv[c];
				}
				else{
					maxi = max(maxi, tree[k-1+dfs[c]]);
					c = parn[c].first;
				}
			}
			maxi = max(maxi, ftree(dfs[c],dfs[b]));
			printf("%d\n",maxi);
		}
	}
	return 0;
}

wnguscjf01 2년 전 0

그냥 단순 실수였네요

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

문제

문제

출처

ICPC

HLD 처음 짜봅니다

wnguscjf01 2년 전 0

wnguscjf01 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말