제출 #1238130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238130		CyberCow	봉쇄 시간 (IOI23_closing)	C++20	0 / 100	1094 ms	31912 KiB

closing

#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 200005;
vector<pair<int, int>> v[N];

ll her[N], her1[N];

void Dfs(int g, int p, ll hh)
{
	her[g] = hh;
	for (auto to : v[g])
	{
		if (to.first != p)
		{
			Dfs(to.first, g, hh + to.second);
		}
	}
}

void Dfs1(int g, int p, ll hh)
{
	her1[g] = hh;
	for (auto to : v[g])
	{
		if (to.first != p)
		{
			Dfs1(to.first, g, hh + to.second);
		}
	}
}

ll maxher[N], maxherpref[N], herpref[N], her1pref[N];

int max_score(int n, int x, int y, long long k, vector<int> u1, vector<int> v1, vector<int> w1)
{
	for (int i = 0; i < n - 1; i++)
	{
		v[v1[i]].push_back({ u1[i], w1[i] });
		v[u1[i]].push_back({ v1[i], w1[i] });
	}
	Dfs(x, -1, 0);
	Dfs1(y, -1, 0);

	vector<ll> ans;
	for (int i = 0; i < n; i++)
	{
		ans.push_back(her[i]);
		ans.push_back(her1[i]);
		maxher[i] = max(her[i], her1[i]);
		if (i == 0)maxherpref[i] = maxher[i];
		else maxherpref[i] = maxherpref[i - 1] + maxher[i];
		if (i == 0)herpref[i] = her[i];
		else herpref[i] = herpref[i - 1] + her[i];
		if (i == 0)her1pref[i] = her1[i];
		else her1pref[i] = her1pref[i - 1] + her1[i];
	}
	sort(ans.begin(), ans.end());
	int qan = 0;
	for (int i = 0; i < ans.size(); i++)
	{
		if (k - ans[i] >= 0)
		{
			qan++;
			k -= ans[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		v[i].clear();
		her[i] = 0;
		her1[i] = 0;
	}
	int obshians = qan;
	for (int i = 0; i <= y; i++)
	{
		for (int j = max(x, i); j < n; j++)
		{
			ll ggum = 0;
			int himikvaqan = (j - i + 1) * 2;
			ggum = maxherpref[j];
			if (i)ggum -= maxherpref[i - 1];
			if (j < y)
			{
				ggum += her1pref[y];
				ggum -= her1pref[j];
			}
			if (x < i)
			{
				ggum += herpref[i - 1];
				ggum -= herpref[x];
			}
			int xx = x;
			if (i < x)xx = i;
			int yy = y;
			if (y < j)yy = j;
			ll kop = k;
			kop -= ggum;
			if (kop < 0)
				continue;
			vector<ll> vvv;
			for (int h = 0; h < xx; h++)
			{
				vvv.push_back(her[h]);
			}
			for (int h = yy + 1; h < n; h++)
			{
				vvv.push_back(her1[h]);
			}
			sort(vvv.begin(), vvv.end());
			for (i = 0; i < vvv.size(); i++)
			{
				if (kop - vvv[i] >= 0)
				{
					kop -= vvv[i];
					himikvaqan++;
				}
			}
			obshians = max(obshians, himikvaqan);
		}
	}
	return obshians;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17