oj.uz

Submission #110539

# Submission time Handle Problem Language Result Execution time Memory
110539 2019-05-11T06:41:19 Z AngusRitossa Designated Cities (JOI19_designated_cities) C++14
6 / 100
 2000 ms 66412 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, pair<int, int> > > adj[200010];
int n;
int dgoingup[200010], dgoingdown[200010], done[200010];
int goingup(int a)
{
	if (dgoingup[a]) return dgoingup[a]-1;
	dgoingup[a] = 1;
	for (auto b : adj[a])
	{
		if (!dgoingup[b.first]) dgoingup[a] += goingup(b.first), dgoingup[a] += b.second.second;
	}
	return dgoingup[a]-1;
}
int goingdown(int a)
{
	if (dgoingdown[a]) return dgoingdown[a]-1;
	dgoingdown[a] = 1;
	for (auto b : adj[a])
	{
		if (!dgoingdown[b.first]) dgoingdown[a] += goingdown(b.first), dgoingdown[a] += b.second.first;
	}
	return dgoingdown[a]-1;
}
int oneans = 1e15;
void findoneans(int a, int above)
{
	done[a] = 1;
	int am = 0;
	for (auto b : adj[a])
	{
		if (done[b.first]) continue;
		am += goingup(b.first)+b.second.second;
	}
	oneans = min(oneans, am+above);
	for (auto b : adj[a])
	{
		if (done[b.first]) continue;
		findoneans(b.first, above+am-goingup(b.first)-b.second.second + b.second.first);
	}
}
int jump[200010][20], root, seen[200010], cost[200010], hei[200010], cost2[200010];
int roots[200010], revroots[200010], upto;
void dfs(int a, int am, int am2)
{
	seen[a] = 1;
	cost[a] = am;
	cost2[a] = am2;
	//printf("%d, %d\n", a, cost[a]);
	for (auto b : adj[a])
	{
		if (seen[b.first]) continue;
		jump[b.first][0] = a;
		hei[b.first] = hei[a]+1;
		dfs(b.first, am+b.second.second, am2+b.second.first);
	}
	if (adj[a].size() == 1)
	{
		roots[a] = upto;
		revroots[upto++] = a;
	}
}
int ans[200010];
int lca(int a, int b)
{
	for (int i = 19; i >= 0; i--)
	{
		if (hei[jump[a][i]] >= hei[b]) a = jump[a][i];
		if (hei[jump[b][i]] >= hei[a]) b = jump[b][i];
	}
	if (a == b) return a;
	for (int i = 19; i >= 0; i--)
	{
		if (jump[a][i] != jump[b][i]) a = jump[a][i], b = jump[b][i];
	}
	assert(a != b && jump[a][0] == jump[b][0]);
	return jump[a][0];
}
int done2[200010], cans, ambelowsave[200010];
int ambelow(int a, int bit)
{
	if (ambelowsave[a]) return ambelowsave[a]-1;
	ambelowsave[a] = 1;
	for (auto b : adj[a])
	{
		if (!ambelowsave[b.first])
		{
			ambelowsave[a] += ambelow(b.first, bit);
		}
	}
	if (adj[a].size() == 1)
	{
		if (bit & (1 << roots[a])) ambelowsave[a]++;
	}
	return ambelowsave[a]-1;
}
void dothing(int a, int amabove, int bit)
{
	done2[a] = bit;
	for (auto b : adj[a])
	{
		if (done2[b.first] == bit) continue;
		amabove += ambelow(b.first, bit);
	}
	for (auto b : adj[a])
	{
		if (done2[b.first] == bit) continue;
		int newamabove = amabove - ambelow(b.first, bit);
		if (newamabove) // goingup
		{
			cans += b.second.first;
		}
		if (newamabove != amabove)
		{
			cans += b.second.second;
		}
		dothing(b.first, newamabove, bit);
	}
}
#undef int
int main()
{
	#define int long long
	scanf("%lld", &n);
	int total = 0;
	for (int i = 1; i < n; i++)
	{
		int a, b, c, d;
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		total += c;
		total += d;
		a--;
		b--;
		adj[a].push_back({ b, { d, c }});
		adj[b].push_back({ a, { c, d }});
	}
	goingup(0), goingdown(0), findoneans(0, 0);
	ans[1] = oneans;
	for (int i = 0; i < n; i++)
	{
		if (adj[i].size() != 1) 
		{
			root = i;
			break;
		}
	}
	hei[root] = 1;
	dfs(root, 0, 0);
	for (int j = 1; j < 20; j++)
	{
		for (int i = 0; i < n; i++)
		{
			jump[i][j] = jump[jump[i][j-1]][j-1];
		}
	}
	fill_n(ans+2, upto-2, (int)(1e15));
	for (int bit = 0; bit < (1 << upto); bit++)
	{
		if (__builtin_popcountll(bit) <= 1) continue;
		cans = 0;
		fill_n(ambelowsave, n, 0);
		ambelow(root, bit);
		dothing(root, 0, bit);
		ans[__builtin_popcountll(bit)] = min(ans[__builtin_popcountll(bit)], total-cans);
	}
	int q;
	scanf("%lld", &q);
	for (int i = 0; i < q; i++)
	{
		int a;
		scanf("%lld", &a);
		printf("%lld\n", ans[a]);
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a);
   ~~~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 23 ms 5188 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Execution timed out 2039 ms 66348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Execution timed out 2032 ms 66412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 23 ms 5188 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Execution timed out 2028 ms 5760 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Execution timed out 2039 ms 66348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 23 ms 5188 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Execution timed out 2039 ms 66348 KB Time limit exceeded
14 Halted 0 ms 0 KB -