QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309702#8134. LCA Countingucup-team1303#WA 1ms5700kbC++201.6kb2024-01-20 20:04:402024-01-20 20:04:41

Judging History

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

  • [2024-01-20 20:04:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5700kb
  • [2024-01-20 20:04:40]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 2e5 + 10;
int n, f[N], s, g[N];
vector <int> v[N];
void dfs(int x) {
	if (v[x].empty()) {
		f[x] = 1;
		s++;
		return;
	}
	int mx1 = 0, mx2 = 0, c = 0;
	for (int i: v[x]) {
		dfs(i);
		if (v[i].size() > 1) c++;
		g[x] += g[i];
		if (f[i] > mx1) mx2 = mx1, mx1 = f[i];
		else chkmax(mx2, f[i]);
	}
	f[x] = mx1 + mx2;
	g[x] += max(0, c - 2);
	// if (v[x].size() > 1) g[x] += v[x].size() - 2;
}
signed main() {
	read(n);
	F(i, 2, n) {
		int x;
		read(x);
		v[x].push_back(i);
	}
	dfs(1);
	// debug << f[1] << endl;
	F(i, 1, f[1]) {
		// if (i <= f[1]) 
		cout << 2 * i - 1 << ' ';
		// else cout << 2 * f[1] - 1 + i - f[1] << ' ';
	}
	// debug << f[1] << endl;
	int res = 0, c = 0, ans = f[1] - 1;
	F(i, f[1] + 1, s) {
		res++;
		if (res == 2) {
			if (++c <= g[1]) ans++;
		}
		cout << i + ans << ' ';
	}
	return 0;
}
/* why?
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3660kb

input:

7
1 1 2 4 2 2

output:

1 3 5 6 

result:

ok 4 number(s): "1 3 5 6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 5 6 7 8 9 

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 5620kb

input:

10
1 2 2 4 5 6 1 2 4

output:

1 3 5 7 8 

result:

ok 5 number(s): "1 3 5 7 8"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

10
1 2 3 3 3 5 6 4 9

output:

1 3 4 

result:

ok 3 number(s): "1 3 4"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 5696kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...

output:

1 3 5 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 ...

result:

wrong answer 8th numbers differ - expected: '13', found: '12'