oj.uz

Submission #30583

# Submission time Handle Problem Language Result Execution time Memory
30583 2017-07-25T06:49:39 Z kajebiii None (KOI16_tree) C++14
9 / 100
 933 ms 45348 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -