#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
vector<int> adj[200010];
vector<int> indonother[200010];
int n, val[200010], m;
int rangetreeleft[17500010];
int rangetreeright[17500010];
int rangetreeval[17500010];
int upto;
void setto1(int node, int curr, int oldcurr, int cstart = 0, int cend = 200010)
{
if (cstart == cend)
{
rangetreeval[curr] = 1;
return;
}
int mid = (cstart+cend)/2;
if (node <= mid)
{
rangetreeleft[curr] = ++upto;
rangetreeright[curr] = rangetreeright[oldcurr];
setto1(node, rangetreeleft[curr], rangetreeleft[oldcurr], cstart, mid);
}
else
{
rangetreeright[curr] = ++upto;
rangetreeleft[curr] = rangetreeleft[oldcurr];
setto1(node, rangetreeright[curr], rangetreeright[oldcurr], mid+1, cend);
}
rangetreeval[curr] = max(0, rangetreeval[rangetreeleft[curr]]) + max(0, rangetreeval[rangetreeright[curr]]);
}
void setto0(int s, int e, int curr, int oldcurr, int cstart = 0, int cend = 200010)
{
// also, conveniently, sets e+1 to 1
rangetreeval[curr] = rangetreeval[oldcurr];
if (s <= cstart && cend <= e)
{
rangetreeval[curr] = -1;
return;
}
int mid = (cstart+cend)/2;
if (e <= mid)
{
rangetreeleft[curr] = ++upto;
rangetreeright[curr] = rangetreeright[oldcurr];
setto0(s, e, rangetreeleft[curr], rangetreeleft[oldcurr], cstart, mid);
if (e == mid)
{
rangetreeright[curr] = ++upto;
setto1(e+1, rangetreeright[curr], rangetreeright[oldcurr], mid+1, cend);
}
}
else if (s > mid)
{
rangetreeright[curr] = ++upto;
rangetreeleft[curr] = rangetreeleft[oldcurr];
setto0(s, e, rangetreeright[curr], rangetreeright[oldcurr], mid+1, cend);
}
else
{
rangetreeleft[curr] = ++upto;
rangetreeright[curr] = ++upto;
setto0(s, e, rangetreeleft[curr], rangetreeleft[oldcurr], cstart, mid);
setto0(s, e, rangetreeright[curr], rangetreeright[oldcurr], mid+1, cend);
}
rangetreeval[curr] = rangetreeval[curr] == -1 ? 0 : max(0, rangetreeval[rangetreeleft[curr]]) + max(0, rangetreeval[rangetreeright[curr]]);
}
void whichonesare1(int curr, int cstart = 0, int cend = 200010)
{
if (!rangetreeval[curr]) return;
if (cstart == cend) D("is set to 1 %d\n", cstart);
int mid = (cstart+cend)/2;
whichonesare1(rangetreeleft[curr], cstart, mid);
whichonesare1(rangetreeright[curr], mid+1, cend);
}
pair<int, int> maxdis[200010][3];
int seen[200010], leafdis[200010];
int distoleaf(int a)
{
if (seen[a]) return leafdis[a];
seen[a] = 1;
for (auto b : adj[a])
{
if (!seen[b]) leafdis[a] = max(leafdis[a], distoleaf(b));
}
D("distoleaf %d - %d\n", a, leafdis[a]+1);
return ++leafdis[a];
}
void findmxdis(int a, int par = -1, int pardis = 0)
{
maxdis[a][0] = { pardis, (par == -1) ? adj[a].size() : par };
maxdis[a][1].second = maxdis[a][2].second = adj[a].size();
for (int j = 0; j < (int)adj[a].size(); j++)
{
int b = adj[a][j];
if (j != par)
{
pair<int, int> d = { distoleaf(b), j };
if (d > maxdis[a][0])
{
maxdis[a][2] = maxdis[a][1];
maxdis[a][1] = maxdis[a][0];
maxdis[a][0] = d;
}
else if (d > maxdis[a][1])
{
maxdis[a][2] = maxdis[a][1];
maxdis[a][1] = d;
}
else if (d > maxdis[a][2])
{
maxdis[a][2] = d;
}
}
}
for (int j = 0; j < (int)adj[a].size(); j++)
{
int b = adj[a][j];
if (j != par)
{
int newpardis = 0;
if (maxdis[a][0].second != j) newpardis = maxdis[a][0].first;
else if (maxdis[a][1].second != j) newpardis = maxdis[a][1].first;
newpardis++;
findmxdis(b, indonother[a][j], newpardis);
}
}
D("done... %d - %d %d %d\n", a, maxdis[a][0].second, maxdis[a][1].second, maxdis[a][2].second);
}
vector<int> ans[200010];
int saveroots[200010];
int returntree(int a, int b)
{
if (upto >= 17490000) while (1) {}
if (a == 0) return 0;
if (ans[a][b]) return ans[a][b];
D("\n%d %d - %d\n", a, b, adj[a][b]);
int x = 0, y = 1;
if (maxdis[a][x].second == b) x++, y++;
else if (maxdis[a][y].second == b) y++;
D("a %d b %d, x y %d %d - mxdisx %d\n", a, b, x, y, maxdis[a][x].second);
D("%d - %lu\n", maxdis[a][x].second, adj[a].size());
int root = returntree(adj[a][maxdis[a][x].second], indonother[a][maxdis[a][x].second]);
int newroot;
D("a %d b %d - setting %d\n", a, b, maxdis[a][x].first);
if (maxdis[a][y].first)
{
// newroot = ++upto;
D("a %d b %d - setting to 0 - %d to %d\n", a, b, maxdis[a][x].first-maxdis[a][y].first, maxdis[a][x].first-1);
// setto1(maxdis[a][x].first, newroot, root);
//root = newroot;
newroot = ++upto;
setto0(maxdis[a][x].first-maxdis[a][y].first, maxdis[a][x].first-1, newroot, root);
}
else
{
if (root == saveroots[rangetreeval[root]])
{
if (saveroots[rangetreeval[root]+1]) newroot = saveroots[rangetreeval[root]+1];
else
{
newroot = saveroots[rangetreeval[root]+1] = ++upto;
setto1(maxdis[a][x].first, newroot, root);
}
}
else
{
newroot = ++upto;
setto1(maxdis[a][x].first, newroot, root);
}
}
return ans[a][b] = newroot;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
indonother[a].push_back(adj[b].size());
indonother[b].push_back(adj[a].size());
adj[a].push_back(b);
adj[b].push_back(a);
ans[a].push_back(0);
ans[b].push_back(0);
}
distoleaf(1);
findmxdis(1);
for (int i = 1; i <= n; i++) scanf("%d", &val[i]), adj[i].push_back(0), indonother[i].push_back(0);
for (int i = 1; i <= n; i++)
{
ans[i].push_back(0);
ans[i].push_back(0);
adj[i].push_back(0);
indonother[i].push_back(0);
int root = returntree(i, adj[i].size()-1);
printf("%d\n", max(0, min(rangetreeval[root]-1, m)));
// whichonesare1(root);
}
}
Compilation message
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:182:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:196:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; i++) scanf("%d", &val[i]), adj[i].push_back(0), indonother[i].push_back(0);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
15744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
667 ms |
92800 KB |
Output is correct |
| 2 |
Correct |
860 ms |
127708 KB |
Output is correct |
| 3 |
Correct |
162 ms |
39900 KB |
Output is correct |
| 4 |
Correct |
1343 ms |
150564 KB |
Output is correct |
| 5 |
Correct |
1609 ms |
210608 KB |
Output is correct |
| 6 |
Correct |
1546 ms |
203544 KB |
Output is correct |
| 7 |
Correct |
1156 ms |
150388 KB |
Output is correct |
| 8 |
Correct |
1278 ms |
165280 KB |
Output is correct |
| 9 |
Correct |
1495 ms |
161480 KB |
Output is correct |
| 10 |
Correct |
1462 ms |
162992 KB |
Output is correct |
| 11 |
Correct |
789 ms |
137644 KB |
Output is correct |
| 12 |
Correct |
1667 ms |
236348 KB |
Output is correct |
| 13 |
Correct |
1511 ms |
225260 KB |
Output is correct |
| 14 |
Correct |
1459 ms |
228616 KB |
Output is correct |
| 15 |
Correct |
815 ms |
137556 KB |
Output is correct |
| 16 |
Correct |
1394 ms |
212788 KB |
Output is correct |
| 17 |
Correct |
1384 ms |
213320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
976 ms |
122444 KB |
Output is correct |
| 2 |
Correct |
1527 ms |
204668 KB |
Output is correct |
| 3 |
Correct |
194 ms |
43460 KB |
Output is correct |
| 4 |
Correct |
1236 ms |
151200 KB |
Output is correct |
| 5 |
Correct |
1626 ms |
212856 KB |
Output is correct |
| 6 |
Correct |
1394 ms |
201852 KB |
Output is correct |
| 7 |
Correct |
1115 ms |
149380 KB |
Output is correct |
| 8 |
Correct |
1407 ms |
180272 KB |
Output is correct |
| 9 |
Correct |
1383 ms |
172268 KB |
Output is correct |
| 10 |
Correct |
1352 ms |
165980 KB |
Output is correct |
| 11 |
Correct |
929 ms |
142244 KB |
Output is correct |
| 12 |
Correct |
1829 ms |
247160 KB |
Output is correct |
| 13 |
Correct |
1465 ms |
203628 KB |
Output is correct |
| 14 |
Correct |
1396 ms |
228952 KB |
Output is correct |
| 15 |
Correct |
690 ms |
138708 KB |
Output is correct |
| 16 |
Correct |
1438 ms |
218932 KB |
Output is correct |
| 17 |
Correct |
1325 ms |
208740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
15744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
