QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207215 | #6638. Treelection | Alinxester | WA | 100ms | 19712kb | C++14 | 3.0kb | 2023-10-08 11:26:46 | 2023-10-08 11:26:46 |
Judging History
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'