oj.uz

답안 #106046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106046 2019-04-16T09:56:19 Z AngusRitossa Unique Cities (JOI19_ho_t5) C++14
64 / 100
 1829 ms 247160 KB 
#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);
                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 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 -

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 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

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 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

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 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 -