글 읽기 - 어디서 런타임에러가 나는지 모르겠습니다

kdr06006 4년 전 0

HLD로 트리를 분할했고, 쿼리를 미리 받아서 트리를 미리 구축했습니다.

그리고 union-find로 합치면서 갈 수 있는지 여부와 구간 합을 이용해 답을 냈는데 자꾸 런타임에러가 나서 질문드립니다.

노드개수가 30,000개고, 쿼리 수는 300,000개라서 배열 크기가 문제있는건 아닌거같은데 어디서 잘못됐는지 알고싶습니다

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int _size = 3e4 + 1;
int D[_size], dfsn[_size], d_n, cn[_size], c, p[_size], _p[_size];
int head[_size], parent[_size], segment[_size * 4], sz[_size];
typedef struct { char c; int a, b; }Q;
Q q[_size * 10];
vector<int>adj[_size];

inline int get(int x) { return x == _p[x] ? x : _p[x] = get(_p[x]); }
inline void uni(int a, int b) { a < b ? _p[b] = a : _p[a] = b; }

void DFS(int cur, int pre)
{
	sz[cur] = 1;
	for (auto a : adj[cur]) {
		if (a != pre) {
			DFS(a, cur);
			sz[cur] += sz[a];
		}
	}
}

void HLD(int cur, int pre, int depth)
{
	int u = dfsn[cur] = ++d_n;
	D[u] = depth;
	cn[u] = c;
	if (head[c] == 0) head[c] = u;

	int h = 0;
	for (auto a : adj[cur]) {
		if (a == pre) continue;
		if (h == 0 || sz[h] < sz[a]) h = a;
	}
	if (h != 0) {
		HLD(h, cur, depth + 1);
		parent[dfsn[h]] = u;
	}

	for (auto a : adj[cur]) {
		if (a != pre && a != h) {
			c++;
			HLD(a, cur, depth + 1);
			parent[dfsn[a]] = u;
		}
	}
}

int update(int l, int r, int n, int t, int v)
{
	if (t<l || t>r) return segment[n];
	if (l == r) return segment[n] = v;
	int m = l + r >> 1;
	return segment[n] = update(l, m, n << 1, t, v) + update(m + 1, r, n << 1 | 1, t, v);
}

int query(int l, int r, int n, int q_l, int q_r)
{
	if (q_l <= l && r <= q_r) return segment[n];
	if (q_r < l || r < q_l) return 0;
	int m = l + r >> 1;
	return query(l, m, n << 1, q_l, q_r) + query(m + 1, r, n << 1 | 1, q_l, q_r);
}

int ans(int u, int v)
{
	int ret = 0;
	u = dfsn[u], v = dfsn[v];
	while (cn[u] != cn[v]) {
		int uHead = head[cn[u]];
		int vHead = head[cn[v]];
		if (D[uHead] < D[vHead]) {
			ret += query(1, d_n, 1, vHead, v);
			v = parent[vHead];
		}
		else {
			ret += query(1, d_n, 1, uHead, u);
			u = parent[uHead];
		}
	}

	ret += query(1, d_n, 1, min(u, v), max(u, v));
	return ret;
}

int main()
{
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) 
		scanf("%d", &p[i]);
	for (int i = 1; i <= N; i++) _p[i] = i;

	int M;
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		char str[12];
		scanf("%s %d %d", str, &q[i].a, &q[i].b);
		q[i].c = str[0];
		if (q[i].c == 'b') {
			if (get(q[i].a) != get(q[i].b)) {
				adj[q[i].a].push_back(q[i].b);
				adj[q[i].b].push_back(q[i].a);
				uni(get(q[i].a), get(q[i].b));
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		if (sz[i] == 0) 
			DFS(i, 0);
	}
	for (int i = 1; i <= N; i++) {
		if (dfsn[i] == 0) {
			c++;
			HLD(i, 0, 1);
		}
	}

	for (int i = 1; i <= N; i++) 
		update(1, N, 1, dfsn[i], p[i]);
	for (int i = 1; i <= N; i++) _p[i] = i;

	for (int i = 0; i < M; i++) {
		if (q[i].c == 'e') {
			if (get(q[i].a) != get(q[i].b)) printf("impossible\n");
			else printf("%d\n", ans(q[i].a, q[i].b));
		}
		else if (q[i].c == 'b') {
			if (get(q[i].a) != get(q[i].b)) {
				printf("yes\n");
				uni(get(q[i].a), get(q[i].b));
			}
			else printf("no\n");
		}
		else {
			p[i] = q[i].b;
			update(1, N, 1, dfsn[q[i].a], p[i]);
		}
	}
}

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

문제

문제

출처

ICPC

어디서 런타임에러가 나는지 모르겠습니다

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말