Submission #106046

#	Time	Username	Problem	Language	Result	Execution time	Memory
106046		AngusRitossa	Unique Cities (JOI19_ho_t5)	C++14	64 / 100	1829 ms	247160 KiB

joi2019_ho_t5

#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 (stderr)

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);
                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32