답안 #30583 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30583	2017-07-25T06:49:39 Z	kajebiii	트리 (KOI16_tree)	C++14	9 / 100	933 ms	45348 KB

tree

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e5 + 100, MAX_Q = 2e5 + 100, LOG_N = 21;

int N, Q, iP[MAX_N], Nr[MAX_Q][4];
vector<int> Ed[MAX_N];
int P[LOG_N][MAX_N], D[MAX_N], S[MAX_N];
int predfs(int v, int p) {
	D[v] = D[p] + 1; S[v] = 1; P[0][v] = p;
	for(int w : Ed[v]) if(w != p) S[v] += predfs(w, v);
	return S[v];
}

struct BIT {
	int val[MAX_N];
	BIT() {memset(val, 0, sizeof(val));}
	void update(int v, int k) {for(v+=10; v<MAX_N; v+=v&-v) val[v]+=k;}
	int getSum(int v) {int res=0; for(v+=10; v; v-=v&-v) res+=val[v]; return res;}
	int getSum(int a, int b) {return getSum(b) - getSum(a-1);}
}bit;
int eN = 0;
int eIx[MAX_N], fIx[MAX_N];
void makedfs(int v, int p, int h) {
//	printf("%d %d %d\n", v, p, h);
	if(v != N/2) bit.update(eN, 1), eIx[v] = eN++; fIx[v] = h;
	int ix = -1;
	for(int w : Ed[v]) if(w != p && (ix == -1 || S[ix] < S[w])) ix = w;
	if(ix == -1) return;
	makedfs(ix, v, h);
	for(int w : Ed[v]) if(w != p && w != ix) makedfs(w, v, w);
}
int getL(int a, int b) {
	if(D[a] > D[b]) swap(a, b);
	for(int p=LOG_N-1; p>=0; p--) if((D[b]-D[a])&(1<<p)) b=P[p][b];
	if(a == b) return a;
	for(int p=LOG_N-1; p>=0; p--) if(P[p][a]!=P[p][b]) a=P[p][a], b=P[p][b];
	return P[0][a];
}
bool isCan(int fr, int to) {
	int hd = fIx[fr];
	if(D[to] < D[hd]) {
		int val = bit.getSum(eIx[hd], eIx[fr]);
		if(val != D[fr] - D[hd] + 1) return false;
		return isCan(P[0][hd], to);
	} else {
		int val = bit.getSum(eIx[fr] - (D[fr] - D[to]) + 1, eIx[fr]);
		return val == (D[fr] - D[to]);
	}
	printf("what?\n");
	return false;
}
int main() {
	cin >> N >> Q;
	for(int i=2; i<=N; i++) scanf("%d", &iP[i]);
	for(int i=2; i<=N; i++) Ed[i].push_back(iP[i]), Ed[iP[i]].push_back(i);
	predfs(N/2, 0);
	for(int p=1; p<LOG_N; p++) for(int i=1; i<=N; i++) P[p][i] = P[p-1][P[p-1][i]];
	makedfs(N/2, 0, N/2);
	for(int q=1; q<=Q; q++) {
		int b, c, d; scanf("%d%d%d", &b, &c, &d);
		int l = getL(b, c);
//		printf("[%d %d -> %d]\n", b, c, l);
//		printf("b %d | c %d\n", isCan(b, l), isCan(c, l));
		bool ans = (isCan(b, l) & isCan(c, l));
		puts(ans?"YES":"NO");
		if(d == 1) {
			int x = b, y = iP[b];
			if(!ans) x = c, y = iP[c];
			if(D[x] > D[y]) swap(x, y);
			if(y == 1 || bit.getSum(eIx[y], eIx[y]) == 0) continue;
			bit.update(eIx[y], -1);
		}
	}
	return 0;
}

Compilation message

tree.cpp: In function 'int main()':
tree.cpp:69:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=2; i<=N; i++) scanf("%d", &iP[i]);
                                             ^
tree.cpp:75:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int b, c, d; scanf("%d%d%d", &b, &c, &d);
                                           ^

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	30940 KB	Output is correct
2	Correct	0 ms	30940 KB	Output is correct
3	Correct	0 ms	30940 KB	Output is correct
4	Correct	0 ms	30940 KB	Output is correct
5	Correct	3 ms	30940 KB	Output is correct
6	Correct	0 ms	30940 KB	Output is correct
7	Correct	0 ms	30940 KB	Output is correct
8	Correct	3 ms	30940 KB	Output is correct
9	Correct	0 ms	30940 KB	Output is correct
10	Correct	0 ms	30940 KB	Output is correct

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	30940 KB	Output is correct
2	Correct	0 ms	30940 KB	Output is correct
3	Correct	0 ms	30940 KB	Output is correct
4	Correct	0 ms	30940 KB	Output is correct
5	Correct	3 ms	30940 KB	Output is correct
6	Correct	0 ms	30940 KB	Output is correct
7	Correct	0 ms	30940 KB	Output is correct
8	Correct	3 ms	30940 KB	Output is correct
9	Correct	0 ms	30940 KB	Output is correct
10	Correct	0 ms	30940 KB	Output is correct
11	Correct	0 ms	30940 KB	Output is correct
12	Correct	0 ms	30940 KB	Output is correct
13	Correct	3 ms	30940 KB	Output is correct
14	Correct	0 ms	30940 KB	Output is correct
15	Correct	0 ms	30940 KB	Output is correct
16	Correct	0 ms	30940 KB	Output is correct
17	Correct	3 ms	30940 KB	Output is correct
18	Correct	0 ms	30940 KB	Output is correct
19	Incorrect	3 ms	30940 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	30940 KB	Output is correct
2	Correct	0 ms	30940 KB	Output is correct
3	Correct	0 ms	30940 KB	Output is correct
4	Correct	0 ms	30940 KB	Output is correct
5	Correct	3 ms	30940 KB	Output is correct
6	Correct	0 ms	30940 KB	Output is correct
7	Correct	0 ms	30940 KB	Output is correct
8	Correct	3 ms	30940 KB	Output is correct
9	Correct	0 ms	30940 KB	Output is correct
10	Correct	0 ms	30940 KB	Output is correct
11	Correct	0 ms	30940 KB	Output is correct
12	Correct	0 ms	30940 KB	Output is correct
13	Correct	3 ms	30940 KB	Output is correct
14	Correct	0 ms	30940 KB	Output is correct
15	Correct	0 ms	30940 KB	Output is correct
16	Correct	0 ms	30940 KB	Output is correct
17	Correct	3 ms	30940 KB	Output is correct
18	Correct	0 ms	30940 KB	Output is correct
19	Incorrect	3 ms	30940 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	30940 KB	Output is correct
2	Correct	0 ms	30940 KB	Output is correct
3	Correct	0 ms	30940 KB	Output is correct
4	Correct	0 ms	30940 KB	Output is correct
5	Correct	3 ms	30940 KB	Output is correct
6	Correct	0 ms	30940 KB	Output is correct
7	Correct	0 ms	30940 KB	Output is correct
8	Correct	3 ms	30940 KB	Output is correct
9	Correct	0 ms	30940 KB	Output is correct
10	Correct	0 ms	30940 KB	Output is correct
11	Correct	683 ms	43676 KB	Output is correct
12	Correct	789 ms	45340 KB	Output is correct
13	Correct	843 ms	45284 KB	Output is correct
14	Correct	933 ms	42124 KB	Output is correct
15	Correct	773 ms	44936 KB	Output is correct
16	Correct	813 ms	45348 KB	Output is correct
17	Correct	469 ms	42920 KB	Output is correct
18	Incorrect	439 ms	43492 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	30940 KB	Output is correct
2	Correct	0 ms	30940 KB	Output is correct
3	Correct	0 ms	30940 KB	Output is correct
4	Correct	0 ms	30940 KB	Output is correct
5	Correct	3 ms	30940 KB	Output is correct
6	Correct	0 ms	30940 KB	Output is correct
7	Correct	0 ms	30940 KB	Output is correct
8	Correct	3 ms	30940 KB	Output is correct
9	Correct	0 ms	30940 KB	Output is correct
10	Correct	0 ms	30940 KB	Output is correct
11	Correct	0 ms	30940 KB	Output is correct
12	Correct	0 ms	30940 KB	Output is correct
13	Correct	3 ms	30940 KB	Output is correct
14	Correct	0 ms	30940 KB	Output is correct
15	Correct	0 ms	30940 KB	Output is correct
16	Correct	0 ms	30940 KB	Output is correct
17	Correct	3 ms	30940 KB	Output is correct
18	Correct	0 ms	30940 KB	Output is correct
19	Incorrect	3 ms	30940 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

답안 #30583

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 13.0

Subtask #3 0 / 14.0

Subtask #4 0 / 19.0

Subtask #5 0 / 45.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 13.0

Subtask #3
0 / 14.0

Subtask #4
0 / 19.0

Subtask #5
0 / 45.0