글 읽기 - 16%에서 틀렸습니다가 뜹니다.

dhsrhkdgus 6년 전 0

Persistent segment tree를 구현한 코드입니다.

Fast IO를 안쓰면 TLE가 뜬다고는 하는데 그 이전에 그냥 WA가 뜨네요.

테스트케이스 여러 개 만들어서 해봤을 때 모두 맞았는데 어떤 부분이 틀렸는지 못찾겠습니다.

(cn은 weight를 compress했을 때 개수입니다. 이 문제에서는 다 다르다 했으니까 n이 될거에요)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <unordered_map>
#include <list>
#include <time.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define Fi first
#define Se second
#define pb push_back
#define mp make_pair
#define rep(pos, len) for(int pos=0;pos<len;pos++)
#define repp(pos, len) for(int pos=1;pos<=len;pos++)
#define all(x) x.begin(), x.end()

#define ABS(x) (((x) > 0 ) ? (x) : (-(x)))
#define MAX2(x, y) (((x) > (y)) ? (x) : (y))
#define MIN2(x, y) (((x) < (y)) ? (x) : (y))
#define MAX3(x, y, z) ( (x) > (y)  ? ( (x) > (z) ? (x) : (z)  ) : ( (y) > (z) ? (y) : (z) )  )
#define MIN3(x, y, z) ( (x) < (y)  ? ( (x) < (z) ? (x) : (z)  ) : ( (y) < (z) ? (y) : (z) )  )
#define MID3(val1,val2,val3) MAX2(MIN2(MAX2(val1,val2),val3),MIN2(val1,val2))

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME

#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define getll1(X) scanf("%lld",&X)
#define getll2(X,Y) scanf("%lld%lld",&X,&Y)
#define getll3(X,Y,Z) scanf("%lld%lld%lld",&X,&Y,&Z)
#define getll4(X,Y,Z,W) scanf("%lld%lld%lld%lld",&X,&Y,&Z,&W)
#define getll(...) GET_MACRO(__VA_ARGS__, getll4, getll3, getll2, getll1) (__VA_ARGS__)

#define dout(n) printf("%d\n",n)
#define lldout(n) printf("%lld\n",n)

// 1-index
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)

#define INF 1987654321
#define IINF 98765432198765432

const int MAXN = 1e5 + 50;
const int LOGN = 17;

int par[MAXN][LOGN], level[MAXN];
int w[MAXN], RM[MAXN];    // RM: reverse of map M
map<int, int> M;
vector<int> adj[MAXN];
int n, cn;


// persistent segment tree
struct node {
	int count;
	node *left, *right;
	node() {
		count = 0;
		left = right = NULL;
	}
};

node *root[MAXN];
node *start;

void init(node *cur, int l, int r) {
	if(l+1 == r) return;
	int m = (l + r) >> 1;
	cur->left = new node();
	cur->right = new node();
	init(cur->left, l, m);
	init(cur->right, m, r);
}

void add(int l, int r, int w, node *cur, node *p) {
	if(l+1 == r) {
		cur->count = p->count + 1;
		return;
	}

	int m = (l + r) >> 1;
	if(l <= w and w < m) {
		cur->right = p->right;
		cur->left = new node();
		add(l, m, w, cur->left, p->left);
	} else {
		cur->left = p->left;
		cur->right = new node();
		add(m, r, w, cur->right, p->right);
	}

	cur->count = cur->left->count + cur->right->count;
}

void dfs(int node, int pnode) {
	add(0, cn, M[w[node]], root[node], (pnode == -1) ? start : root[pnode]);
	for(auto &cnode : adj[node]) {
		if(cnode != pnode)
			dfs(cnode, node);
	}
}

// find LCA
void dfsLevel(int node, int pnode) {
	for(auto &cnode : adj[node]) {
		if(cnode != pnode) {
			level[cnode] = level[node] + 1;
			par[cnode][0] = node;
			dfsLevel(cnode, node);
		}
	}
}

void preprocess() {
	par[0][0] = 0;
	level[0] = 0;
	dfsLevel(0, -1);
	for(int i = 1; i < LOGN; i++) {
		rep(node, n) {
			par[node][i] = par[par[node][i-1]][i-1];
		}
	}
}

int lca(int u, int v) {
	if(level[u] > level[v]) swap(u, v);
	int d = level[v] - level[u];
	for(int i = 0; i < LOGN; i++) {
		if(d & (1 << i))
			v = par[v][i];
	}

	for(int i = LOGN - 1; i >= 0; i--) {
		if(par[u][i] != par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}


// answer query
int query(node *u, node *v, node *lca, node *p, int l, int r, int k) {
	if(l+1 == r)
		return l;

	int cnt = u->left->count + v->left->count - lca->left->count - p->left->count;
	int m = (l + r) >> 1;
	if(cnt >= k)
		return query(u->left, v->left, lca->left, p->left, l, m, k);
	else
		return query(u->right, v->right, lca->right, p->right, m, r, k - cnt);
}



int main() {
	int Q;
	geti(n, Q);
	rep(i, n) {
		geti(w[i]);
		M[w[i]];
	}

	cn = 0;
	for(auto &e : M) {
		M[e.first] = cn;
		RM[cn] = e.first;
		cn++;
	}

	rep(i, n-1) {
		int u, v;
		geti(u, v);
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	preprocess();
	start = new node();
    init(start, 0, cn);
	rep(i, n) root[i] = new node();
	dfs(0, -1);

	while(Q--) {
		int u, v, k;
		geti(u, v, k);
		u--; v--;
		int lc = lca(u, v);
		node *p = (lc == par[lc][0]) ? start : root[par[lc][0]];
		int ans = query(root[u], root[v], root[lc], p, 0, cn, k);
		dout(RM[ans]);
	}
}

dongwon0427 6년 전 0

저도 16%에서 시간 초과가 나요.. ㅜㅜ 왜이러지

dongwon0427 6년 전 1

저같은 경우는 완전히 틀리게 식을 써놨었네요 ㅎㅎ;

16%까지는 그냥 진행되는 건가봐요. 실수로 freopen을 안 지웠을때도 16%까지는 맞더라구요

dhsrhkdgus 6년 전 0

그렇군요 다시 확인해봐야겠네요

정보 감사합니다

dongwon0427 6년 전 1

LCA 함수를 보니까

두 노드들이 조상 관계일 때 예외처리를 안 하신 것 같네요.

그 경우에는 이미 두 노드들이 같기 때문에

두번째 루프에서 더 올라가지 않게 되고

LCA의 조상이 리턴됩니다

dhsrhkdgus 6년 전 0

아 u==v 빼먹었네요ㅋㅋ

if(u==v) return u

추가하니까 맞았습니다 나왔네요

감사합니다~

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

문제

문제

출처

ICPC

16%에서 틀렸습니다가 뜹니다.

dhsrhkdgus 6년 전 0

dongwon0427 6년 전 0

dongwon0427 6년 전 1

dhsrhkdgus 6년 전 0

dongwon0427 6년 전 1

dhsrhkdgus 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말