oj.uz

Submission #110544

# Submission time Handle Problem Language Result Execution time Memory
110544 2019-05-11T06:48:59 Z AngusRitossa Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 67028 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];
}
#undef int
int main()
{
	#define int long long
	scanf("%lld", &n);
	for (int i = 1; i < n; i++)
	{
		int a, b, c, d;
		scanf("%lld%lld%lld%lld", &a, &b, &c, &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);
	jump[root][0] = root;
	for (int j = 1; j < 20; j++)
	{
		for (int i = 0; i < n; i++)
		{
			jump[i][j] = jump[jump[i][j-1]][j-1];
		}
	}
	set<int> in;
	for (int i = 0; i < upto; i++) in.insert(i);
	for (int i = upto-1; i > 1; i--)
	{
		// want to remove something from in
		int pre = -1;
		pair<int, int> mn = { 1e15, -1 };
		for (auto it = in.begin(); it != in.end(); ++it)
		{
			auto nex = next(it);
			int l;
			int extra = 0;
			if (nex == in.end())
			{
				int l1 = lca(revroots[*it], revroots[pre]);
				int l2 = lca(revroots[*in.begin()], revroots[pre]);
				if (hei[l1] < hei[l2]) extra = cost2[l2]-cost2[l1];
				l = l1;
			}
			else if (pre == -1)
			{
				int l2 = lca(revroots[*it], revroots[*nex]);
				int l1 = lca(revroots[*nex], revroots[*in.rbegin()]);
				if (hei[l1] > hei[l2]) extra = cost2[l1]-cost2[l2];
				l = l2;
			}
			else
			{
				int l1 = lca(revroots[*it], revroots[pre]);
				int l2 = lca(revroots[*it], revroots[*nex]);
				if (hei[l1] > hei[l2]) l = l1;
				else l = l2;
			}
			int am = cost[revroots[*it]] - cost[l] + extra;
		//	printf("%lld (%lld) lca %lld, cost %lld\n", *it, revroots[*it], l, am);
			mn = min(mn, { am, *it });
			pre = *it;
		}
		assert(mn.second != -1);
	//	printf("%lld (%lld) %lld\n\n", mn.second, revroots[mn.second], mn.first);
		in.erase(mn.second);
		ans[i] = ans[i+1]+mn.first;
	}
	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:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:89: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:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:163: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 7 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5168 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 8 ms 5040 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
17.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 7 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5168 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 8 ms 5040 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 144 ms 5852 KB Output is correct
14 Correct 9 ms 5888 KB Output is correct
15 Correct 136 ms 5760 KB Output is correct
16 Correct 153 ms 5852 KB Output is correct
17 Correct 156 ms 5816 KB Output is correct
18 Correct 147 ms 5880 KB Output is correct
19 Correct 156 ms 5760 KB Output is correct
20 Correct 187 ms 5884 KB Output is correct
21 Correct 153 ms 5760 KB Output is correct
22 Correct 114 ms 5760 KB Output is correct
23 Correct 233 ms 5880 KB Output is correct
24 Correct 631 ms 6136 KB Output is correct
25 Correct 20 ms 5888 KB Output is correct
26 Correct 788 ms 5884 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Execution timed out 2104 ms 66836 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 7 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5168 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 8 ms 5040 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Execution timed out 2104 ms 66836 KB Time limit exceeded
14 Halted 0 ms 0 KB -