ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208398 | #3792. Water and Ice | _Alexande_ | 100 | 1844ms | 141052kb | C++11 | 5.6kb | 2024-08-02 12:24:55 | 2024-08-02 12:56:16 |
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
#define re register
#define il inline
#define int long long
using namespace std;
const int MAXN = 5e5 + 5;
il int gc() {
static char buf[1000000], *p1 = buf, *p2 = buf;
return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)) ? EOF : *p1++;
//return getchar();
}
il int geti() {
re char ch = gc();
re int f = 1, x = 0;
while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = gc();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = gc();
return f * x;
}
int n, m;
int a[MAXN];
int to[MAXN], nxt[MAXN], head[MAXN], ecnt, ddd[MAXN];
il void Add(re int u, re int v) {
to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
to[++ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt;
}
int dep[MAXN], d;
int stt[21][MAXN], lg2[MAXN], id1[MAXN], tot, id[MAXN];
void DFS1(int u, int last, int depth) {
dep[u] = depth;
stt[0][++tot] = u;
id1[u] = tot;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == last) continue;
DFS1(v, u, depth + 1);
stt[0][++tot] = u;
}
}
il int Lower(re int x, re int y) {
return dep[x] < dep[y] ? x : y;
}
void GetST() {
for (re int i = 2; i <= tot; i++) lg2[i] = lg2[i >> 1] + 1;
for (re int i = 1; (1 << i) <= tot; i++) {
re int w = (1 << i);
for (re int j = 1; j + w - 1 <= tot; j++) {
stt[i][j] = Lower(stt[i - 1][j], stt[i - 1][j + w / 2]);
}
}
}
il int LCA(re int x, re int y) {
x = id1[x]; y = id1[y];
if (x > y) swap(x, y);
int i = lg2[y - x + 1], w = (1 << i);
return Lower(stt[i][x], stt[i][y - w + 1]);
}
il int Dis(re int x, re int y) {
return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}
int size[MAXN], maxs[MAXN];
int dfa[MAXN];
int vis[MAXN];
int dsiz[MAXN];
int DFS2(int u, int last, int tots) {
size[u] = 1;
maxs[u] = 0;
int cen = 0;
for (re int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (vis[v] || v == last) continue;
int vcen = DFS2(v, u, tots);
if (!cen || maxs[vcen] < maxs[cen]) cen = vcen;
size[u] += size[v];
maxs[u] = max(maxs[u], size[v]);
}
maxs[u] = max(maxs[u], tots - size[u]);
if (!cen || maxs[u] < maxs[cen]) cen = u;
return cen;
}
void Divide(int cen, int tots) {
vis[cen] = 1;
dsiz[cen] = tots;
for (re int i = head[cen]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) continue;
int vsize = (size[v] < size[cen]) ? size[v] : (tots - size[cen]);
int vcen = DFS2(v, cen, vsize);
dfa[vcen] = cen;
Divide(vcen, vsize);
}
}
struct Node{
int sum;
Node *ch[2];
};
Node npool[20000000];
int ncnt;
struct SegTree{
Node *rt;
SegTree() {rt = NULL;}
Node *New() {return &npool[ncnt++];}
void Modify(Node *&now, int pos, int k, int l, int r) {
if (!now) now = New();
now->sum += k;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) Modify(now->ch[0], pos, k, l, mid);
else Modify(now->ch[1], pos, k, mid + 1, r);
}
int Query(Node *now, int l, int r, int nl, int nr) {
if (!now) return 0;
if (l == nl && r == nr) return now->sum;
int mid = (nl + nr) >> 1;
if (r <= mid) return Query(now->ch[0], l, r, nl, mid);
else if (l > mid) return Query(now->ch[1], l, r, mid + 1, nr);
return Query(now->ch[0], l, mid, nl, mid) + Query(now->ch[1], mid + 1, r, mid + 1, nr);
}
};
SegTree T1[MAXN], T2[MAXN];
il void Modify(int idx, int val) {
re int now = idx;
while (now) {
int fa = dfa[now];
T1[now].Modify(T1[now].rt, Dis(now, idx), val, 0, dsiz[now]);
if (fa) T2[now].Modify(T2[now].rt, Dis(fa, idx), val, 0, dsiz[fa]);
now = fa;
}
}
il int Query(int idx, int k) {
re int res = 0;
re int now = idx, last = 0;
while (now) {
int d = Dis(idx, now);
if (d > k) {
last = now;
now = dfa[now];
continue;
}
res += T1[now].Query(T1[now].rt, 0, k - d, 0, dsiz[now]);
if (last) res -= T2[last].Query(T2[last].rt, 0, k - d, 0, dsiz[now]);
last = now;
now = dfa[now];
}
return res;
}
void Prework() {
DFS1(1, 0, 0);
GetST();
int cen = DFS2(1, 0, n);
Divide(cen, n);
}
signed main() {
ios :: sync_with_stdio ( false );
cin.tie ( 0 ), cout.tie ( 0 );
cin >> n >> d;
for (re int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
Add(x, y);
}
Prework();
for ( int i = 1; i <= n; i ++ ) {
id[i] = i;
}
sort ( id + 1, id + 1 + n, [] ( int x, int y ) { return dep[x] > dep[y]; } );
int ans = 0;
for ( int i = 1; i <= n; i ++ ) {
int tmp = Query ( id[i], d - 1 );
if ( !tmp ) {
Modify ( id[i], 1 );
ddd[id[i]] = 1;
ans ++;
}
}
/*
for (re int i = 1; i <= m; i++) {
int op = geti(), x = geti(), y = geti();
x ^= ans; y ^= ans;
if (op == 0) {
ans = Query(x, y);
printf("%d\n", ans);
} else {
Modify(x, y - a[x]);
a[x] = y;
}
}
*/
cout << ans << '\n';
for ( int i = 1; i <= n; i ++ ) {
if ( ddd[i] == 1 ) {
cout << i << " ";
}
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 3ms
memory: 9164kb
input:
10 5 3 7 7 10 7 8 9 1 5 4 3 9 7 5 3 2 7 6
output:
2 1 4
result:
ok ok accepted
Test #2:
score: 10
Accepted
time: 0ms
memory: 9160kb
input:
10 4 8 5 8 6 1 8 4 9 5 3 7 10 8 4 7 2 1 7
output:
3 2 3 9
result:
ok ok accepted
Test #3:
score: 10
Accepted
time: 4ms
memory: 9164kb
input:
10 3 7 8 1 10 4 3 1 5 1 7 2 9 1 4 7 2 2 6
output:
4 3 5 6 8
result:
ok ok accepted
Test #4:
score: 10
Accepted
time: 8ms
memory: 10752kb
input:
3000 4 609 550 550 37 550 460 460 2476 2476 822 460 18 822 740 609 1212 822 2274 740 2276 2276 187 4...
output:
778 6 9 10 18 23 36 38 44 45 47 48 52 67 70 73 80 84 90 93 98 99 100 101 102 104 107 109 116 118 119...
result:
ok ok accepted
Test #5:
score: 10
Accepted
time: 4ms
memory: 10444kb
input:
3000 10 29 699 699 832 29 2332 29 1385 699 1783 832 734 1385 1639 734 2853 29 2689 2853 2190 699 558...
output:
220 22 31 61 62 98 108 115 119 137 152 169 170 178 195 221 227 229 249 263 271 278 340 345 353 360 3...
result:
ok ok accepted
Test #6:
score: 10
Accepted
time: 0ms
memory: 10184kb
input:
3000 50 444 813 444 135 813 2265 135 2309 135 914 914 535 135 2055 2055 1225 914 2499 2055 1364 2499...
output:
20 20 90 208 667 789 824 968 1275 1427 1830 1918 2137 2237 2395 2544 2553 2793 2893 2900 2973
result:
ok ok accepted
Test #7:
score: 10
Accepted
time: 618ms
memory: 95320kb
input:
200000 217 31004 146202 108924 82624 43788 48134 199877 157947 92879 87010 198989 49945 175154 66735...
output:
924 279 304 418 471 539 566 713 1079 1355 1747 1882 1970 2494 2523 2890 3235 3626 3759 4069 4162 445...
result:
ok ok accepted
Test #8:
score: 10
Accepted
time: 766ms
memory: 90908kb
input:
200000 475 77454 87171 23492 138432 137402 34171 181862 18661 57910 51505 135417 198061 164845 19388...
output:
394 833 915 982 2281 2467 2531 2673 2886 3423 3484 5294 5459 6264 6530 7016 7839 8016 8484 9339 1085...
result:
ok ok accepted
Test #9:
score: 10
Accepted
time: 142ms
memory: 141052kb
input:
199999 4 1 2 2 3 1 4 4 5 1 6 6 7 1 8 8 9 1 10 10 11 1 12 12 13 1 14 14 15 1 16 16 17 1 18 18 19 1 20...
output:
99999 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67...
result:
ok ok accepted
Test #10:
score: 10
Accepted
time: 299ms
memory: 88736kb
input:
199397 946 29518 79973 29518 71183 71183 194147 29518 156561 156561 196558 196558 25260 29518 198870...
output:
159 52 101 164 243 252 621 1256 3749 5183 7067 7439 7729 7808 8065 9823 9824 9845 10945 11190 13016 ...
result:
ok ok accepted