QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#773164#28. Corporate life (after hostile takover)IBory0 3ms7752kbC++201.4kb2024-11-23 02:37:392024-11-23 02:37:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 02:37:39]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:7752kb
  • [2024-11-23 02:37:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int SZ = 1 << 18;
vector<int> G[2][SZ];
int in[2][SZ], out[2][SZ], dn;

struct Seg {
	vector<int> T[SZ << 1];
	void Build() {
		for (int i = SZ - 1; i > 0; --i) {
			T[i].resize(T[i * 2].size() + T[i * 2 + 1].size());
			merge(T[i * 2].begin(), T[i * 2].end(), T[i * 2 + 1].begin(), T[i * 2 + 1].end(), T[i].begin());
		}
	}
	int Query(int L, int R, int l, int r, int sL = 1, int sR = SZ, int n = 1) {
		if (R < sL || sR < L) return 0;
		if (L <= sL && sR <= R) {
			auto itR = upper_bound(T[n].begin(), T[n].end(), r);
			auto itL = lower_bound(T[n].begin(), T[n].end(), l);
			return itR - itL;
		}
		int mid = (sL + sR) >> 1;
		return (Query(L, R, l, r, sL, mid, n * 2) + Query(L, R, l, r, mid + 1, sR, n * 2 + 1));
	}
} T;

void DFS(int cur, int k) {
	in[k][cur] = ++dn;
	for (int next : G[k][cur]) DFS(next, k);
	out[k][cur] = dn;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int t = 0; t < 2; ++t) {
		for (int i = 2; i <= N; ++i) {
			int p;
			cin >> p;
			G[t][p].push_back(i);
		}
		dn = 0;
		DFS(1, t);
	}

	for (int i = 1; i <= N; ++i) T.T[in[1][i] + SZ - 1].push_back(in[0][i]);
	T.Build();
	return 0;

	for (int i = 1; i <= N; ++i) {
		int l = in[0][i], r = out[0][i];
		int ans = T.Query(in[1][i], out[1][i], l, r) - 1;
		cout << ans << ' ';
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 7752kb

input:

100
63 76 68 34 53 59 51 62 82 2 90 61 40 85 46 23 34 39 73 23 36 35 61 62 53 95 72 77 17 38 44 34 82 16 18 12 53 23 50 22 1 34 95 34 31 42 10 38 17 58 4 99 68 54 31 36 11 32 54 41 42 59 68 27 60 100 11 40 39 53 83 98 50 69 98 42 74 9 95 95 25 42 87 55 90 43 55 75 14 35 60 20 6 12 22 68 13 3 51
82 5...

output:


result:

wrong answer 1st lines differ - expected: '99 13 26 0 0 0 0 0 0 0 16 0 0 ...0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0', found: ''

Subtask #2:

score: 0
Skipped

Dependency #1:

0%