제출 #110553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110553		AngusRitossa	Designated Cities (JOI19_designated_cities)	C++14	22 / 100	1593 ms	88128 KiB

designated_cities

#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]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44