글 읽기 - 염치불구하고.. HLD 코드 한번 봐주시면 감사하겠습니다..

sgc109 7년 전 0

코드가 너무 길어서 봐주시는 분이 계실지는 잘모르겠지만..

최대한 주석을 달아놨습니다. 제가 만들어본 샘플 데이터들은 다 문제없이 잘 돌아가서 어디서 문제가 생기는지 찾기가 쉽지가 않습니다.

부탁드립니다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
const double EPSILON = 1e-9;
const double PI = acos(0.0)*2;
const int MOD = 1000000007;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

int p[100003][18],depth[100003]; // p는 LCA에서 사용하는 부모정보
int w[100003],segIdx[100003]; // w 는 자신을포함한 자손 노드의 수, segIdx 는 특정 노드의 세그먼트트리에서의 인덱스
int t[300003],d[100003],e[100003]; // t 는 세그트리의 노드, d 는 특정번호 간선들의 가중치
int hldId[100003]; // 노드별 간선들을 묶었을때의 묶음번호(각각의 노드에서 부모노드로 가는 간선은 하나이므로 노드번호를 간선을 식별하는데 씀)
vvi group; // 간선들을 실제로 묶은것
vector<piii> G[100003]; // 그래프 정보(인접행렬)
int N,M,root,o,a,b,u,v,c;
int lca(int a, int b){
	if(a==b) return a;
	if(depth[a]>depth[b]) swap(a,b);
	int diff=depth[b]-depth[a];
	for(int i=0;diff;diff>>=1,i++) if(diff&1) b=p[b][i];
	if(a==b) return a;
	for(int i=17;i>=0;i--) if(p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i];
	if(a==b) return a;
	return p[a][0];
}
int dfs(int here, int dad){
	int ret=1;
	for(int i=1;i<18;i++) p[here][i]=p[p[here][i-1]][i-1];
	for(auto it:G[here]){
		int there=it.first;
		if(there==dad) continue;
		p[there][0]=here;
		depth[there]=depth[here]+1;
		d[there]=it.second.first;
		e[it.second.second]=there;
		ret+=dfs(there,here);
	}
	return w[here]=ret;
}
void tBuild(){ // 인덱스트리 초기화
	N--;
	FOR(i,N) t[N+segIdx[i+2]]=d[i+2];
	for(int i=N-1;i>=1;i--) t[i]=max(t[i<<1],t[i<<1|1]);
}
int tQuery(int l, int r){ // 인덱스트리 쿼리
	int ret=-INF;
	for(l+=N,r+=N;l<=r;l>>=1,r>>=1){
		if(l&1) ret=max(ret,t[l++]);
		if(!(r&1)) ret=max(ret,t[r--]);
	}
	return ret;
}
void tUpdate(int pos, int v){ // 인덱스트리 업데이트
	for(t[pos+=N]=v;pos>1;pos>>=1) t[pos>>1]=max(t[pos],t[pos^1]);
}
int visited[100003];
void grouping(){ // bfs로 간선들을 묶음
	queue<int> q;
	q.push(root);
	visited[root]=1;
	while(!q.empty()){
		int here = q.front();
		q.pop();
		for(auto it:G[here]){
			int there=it.first;
			if(visited[there]) continue;
			q.push(there);
			visited[there]=1;
		}
		int parent=p[here][0];
		if(here==root) continue;
		if(w[here]*2>=w[parent]&&parent!=root){
			hldId[here]=hldId[parent];
			group[hldId[here]].pb(here);
		}
		else {
			hldId[here]=group.size();
			group.pb(vi(1));
			group.back()[0]=here;
		}
	}
}
int hldQuery(int u, int v){
	int ret=-INF;
	int l=lca(u,v);
	while(u!=l){
		if(hldId[u]!=hldId[l]){
			ret=max(ret,tQuery(segIdx[u],segIdx[group[hldId[u]][0]]));
			u=p[group[hldId[u]][0]][0];	
		}
		else{
			int next=depth[u]-depth[l]-1;
			ret=max(ret,tQuery(segIdx[group[hldId[u]].back()],segIdx[group[hldId[u]][group[hldId[u]].size()-1-next]]));
			break;
		}
	}
	while(v!=l){
		if(hldId[v]!=hldId[l]){
			ret=max(ret,tQuery(segIdx[v],segIdx[group[hldId[v]][0]]));
			v=p[group[hldId[v]][0]][0];
		}
		else{
			int next=depth[v]-depth[l]-1;
			ret=max(ret,tQuery(segIdx[group[hldId[v]].back()],segIdx[group[hldId[v]][group[hldId[v]].size()-1-next]]));
			break;
		}
	}
	
	return ret;
}
void hldUpdate(int pos, int v){
	tUpdate(segIdx[e[pos]],v);
}

int main() {
	root=1;
	inp1(N);
	FOR(i,N-1){
		inp3(u,v,c);
		G[u].pb({v,{c,i+1}}); // 각각의 노드번호로 간선번호를 식별하기위해 간선번호도 넣어주고 나중에 dfs돌때 씀
		G[v].pb({u,{c,i+1}});
	}
	dfs(1,0);
	hldId[1]=-1;
	grouping();
	int id=0;
	for(auto g:group){
		for(int i=sz(g)-1;i>=0;i--){
			segIdx[g[i]]=id++;
		}
	}
	tBuild();
	inp1(M);
	FOR(i,M){
		inp3(a,b,c);
		if(a-1) printf("%d\n",hldQuery(b,c));
		else hldUpdate(b,c);
	}
	return 0;
}

dongwon0427 6년 전 1

혹시 어떻게 고쳐서 맞으셨는지 물어볼 수 있을까요..

저도 만드는 데이터마다 다 맞는데 제출만 하면 틀리네요..

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

문제

문제

출처

ICPC

염치불구하고.. HLD 코드 한번 봐주시면 감사하겠습니다..

sgc109 7년 전 0

dongwon0427 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말