QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207215#6638. TreelectionAlinxesterWA 100ms19712kbC++143.0kb2023-10-08 11:26:462023-10-08 11:26:46

Judging History

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

  • [2023-10-08 11:26:46]
  • 评测
  • 测评结果:WA
  • 用时:100ms
  • 内存:19712kb
  • [2023-10-08 11:26:46]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod ((int)1e9 + 9)
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
#define sqr(x) ((x) * (x))
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l, r)(rng);}
template<typename T> inline void read (T &t) {
	t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
	while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
	while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
	if (ch == '.') {
		ch = getchar();
		while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
	}
	t = (f ? -t : t);
}
template <typename T, typename... Args>
	inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
	if (x >= 10) write(x / 10);
	cout << (ll) (x % 10);
}
const int N = 1e6 + 2;
int f[N], g[N], Size[N], fath[N], n;
int head[N], pos;
struct Edge { int to, next; }edge[N << 1];
inline void add_edge (int u, int v) {
	edge[++pos] = (Edge) {v, head[u]}, head[u] = pos; }
inline void get_size (int u) {
	Size[u] = 1;
	go (i, u) {
		int v = edge[i].to;
		get_size(v);
		Size[u] += Size[v];
	}
}
inline void dfs (int u, int x) {
	go (i, u) {
		int v = edge[i].to;
		dfs(v, x);
	}
	if (u > 1) {
		f[u] = max(0ll, f[u] - x);
		//cout << u << " " << fath[u] << " " << f[u] + 1 << '\n';
		f[fath[u]] += f[u] + 1;
	}
}
inline int check (int x) {
	rep (i, 1, n) f[i] = 0;
	dfs(1, x);
	if (f[1] <= x) return 1;
	return 0;
}
inline void pre () {
	rep (i, 1, n) head[i] = g[i] = 0;
	pos = 0;
}
inline void solveg (int u) {
	g[u] = ((g[fath[u]] && f[u]) || (u == 1));
	go (i, u) {
		int v = edge[i].to;
		solveg(v);
	}
}
inline void solve () {
	read(n);
	pre();
	rep (i, 2, n) read(fath[i]), add_edge(fath[i], i);
	get_size(1);
	int l = 1, r = n, ret = n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	//cout << "dkshajashndka : " << '\n';
	dfs(1, ret - 1);
	/*cout << ret << '\n';
	rep (i, 1, n) cout << f[i] << " ";
	cout << '\n';*/
	if (f[1] == ret) solveg(1);
	rep (i, 1, n) {
		if (Size[i] > ret + 1 || (Size[i] == ret + 1 && g[i])) printf("1");
		else printf("0");
	}
	printf("\n");
}
signed main () {
	//freo();
	int _ = 1;
	read(_);
	while (_--) solve();
return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 13756kb

input:

2
4
1 2 3
5
1 1 2 2

output:

1100
10000

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 100ms
memory: 19712kb

input:

10
100000
1 2 3 4 5 6 7 8 9 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 10...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

wrong answer 1st lines differ - expected: '111111111111111111111111111111...0000000000000000000000000000000', found: '111111111111111111111111111111...0000000000000000000000000000000'