oj.uz

Submission #110553

# Submission time Handle Problem Language Result Execution time Memory
110553 2019-05-11T06:57:49 Z AngusRitossa Designated Cities (JOI19_designated_cities) C++14
22 / 100
 1593 ms 88128 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];
}
set<int> in;
int amof[200010];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
void calc(set<int>::iterator it)
{
	auto nex = next(it);
	int l;
	int extra = 0;
	int pre = -1;
	if (it != in.begin()) pre = *prev(it);
	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;
	amof[*it] = am;
	pq.emplace(am, *it);
}
#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];
		}
	}
	for (int i = 0; i < upto; i++) in.insert(i);
	for (int i = upto-1; i > 1; i--)
	{
		// want to remove something from in
		if (i == upto-1)
		{
			for (auto it = in.begin(); it != in.end(); ++it)
			{
				calc(it);
			}
		}
		while (pq.size() && amof[pq.top().second] != pq.top().first) pq.pop();
		pair<int, int> mn = pq.top();
		assert(mn.second != -1);
	//	printf("%lld (%lld) %lld\n\n", mn.second, revroots[mn.second], mn.first);
		in.erase(mn.second);
		auto it = in.lower_bound(mn.second);
		if (it != in.end())
		{
			calc(it);
		}
		if (it != in.begin())
		{
			--it;
			calc(it);
		}
		amof[mn.second] = -1;
		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:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:124: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:180:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:184: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 5148 KB Output is correct
2 Correct 6 ms 5084 KB Output is correct
3 Correct 6 ms 5152 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 6 ms 5092 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 1339 ms 69432 KB Output is correct
3 Correct 690 ms 74192 KB Output is correct
4 Correct 902 ms 69796 KB Output is correct
5 Correct 1287 ms 71832 KB Output is correct
6 Correct 1275 ms 72112 KB Output is correct
7 Correct 1405 ms 75664 KB Output is correct
8 Correct 804 ms 77044 KB Output is correct
9 Correct 1541 ms 82608 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 1223 ms 69392 KB Output is correct
3 Correct 713 ms 81784 KB Output is correct
4 Correct 1012 ms 74328 KB Output is correct
5 Correct 1257 ms 77532 KB Output is correct
6 Correct 1336 ms 78060 KB Output is correct
7 Correct 1593 ms 86788 KB Output is correct
8 Correct 1188 ms 82924 KB Output is correct
9 Correct 1558 ms 88128 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5148 KB Output is correct
2 Correct 6 ms 5084 KB Output is correct
3 Correct 6 ms 5152 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 6 ms 5092 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Incorrect 14 ms 5760 KB Output isn't correct
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 Correct 1339 ms 69432 KB Output is correct
3 Correct 690 ms 74192 KB Output is correct
4 Correct 902 ms 69796 KB Output is correct
5 Correct 1287 ms 71832 KB Output is correct
6 Correct 1275 ms 72112 KB Output is correct
7 Correct 1405 ms 75664 KB Output is correct
8 Correct 804 ms 77044 KB Output is correct
9 Correct 1541 ms 82608 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 1223 ms 69392 KB Output is correct
12 Correct 713 ms 81784 KB Output is correct
13 Correct 1012 ms 74328 KB Output is correct
14 Correct 1257 ms 77532 KB Output is correct
15 Correct 1336 ms 78060 KB Output is correct
16 Correct 1593 ms 86788 KB Output is correct
17 Correct 1188 ms 82924 KB Output is correct
18 Correct 1558 ms 88128 KB Output is correct
19 Correct 6 ms 5120 KB Output is correct
20 Correct 1226 ms 75912 KB Output is correct
21 Correct 729 ms 81920 KB Output is correct
22 Correct 1000 ms 74324 KB Output is correct
23 Incorrect 1242 ms 76392 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5148 KB Output is correct
2 Correct 6 ms 5084 KB Output is correct
3 Correct 6 ms 5152 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 6 ms 5092 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 1339 ms 69432 KB Output is correct
14 Correct 690 ms 74192 KB Output is correct
15 Correct 902 ms 69796 KB Output is correct
16 Correct 1287 ms 71832 KB Output is correct
17 Correct 1275 ms 72112 KB Output is correct
18 Correct 1405 ms 75664 KB Output is correct
19 Correct 804 ms 77044 KB Output is correct
20 Correct 1541 ms 82608 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Correct 1223 ms 69392 KB Output is correct
23 Correct 713 ms 81784 KB Output is correct
24 Correct 1012 ms 74328 KB Output is correct
25 Correct 1257 ms 77532 KB Output is correct
26 Correct 1336 ms 78060 KB Output is correct
27 Correct 1593 ms 86788 KB Output is correct
28 Correct 1188 ms 82924 KB Output is correct
29 Correct 1558 ms 88128 KB Output is correct
30 Correct 6 ms 5120 KB Output is correct
31 Incorrect 14 ms 5760 KB Output isn't correct
32 Halted 0 ms 0 KB -