Submission #919701

#	Time	Username	Problem	Language	Result	Execution time	Memory
919701		prvocislo	Closing Time (IOI23_closing)	C++17	8 / 100	104 ms	34256 KiB

closing

#include "closing.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

vector<vector<pair<int, int> > > g;
void dfs(int u, vector<ll> &c, int p = -1)
{
	for (pair<int, int> v : g[u]) if (v.first != p)
	{
		c[v.first] = c[u] + v.second;
		dfs(v.first, c, u);
	}
}
ll score(set<pair<ll, int> >& s)
{
	return (s.empty() ? 1e18 : s.begin()->first);
}
int max_score(int n, int x, int y, ll k, vector<int> U, vector<int> V, vector<int> W)
{
	g.assign(n, {});
	for (int i = 0; i < n - 1; i++) g[U[i]].push_back({ V[i], W[i] }), g[V[i]].push_back({ U[i], W[i] });
	vector<ll> cx(n), cy(n);
	vector<int> ansx(n, 0), ansy(n, 0);
	dfs(x, cx, -1);
	dfs(y, cy, -1);
	set<pair<ll, int> > px;
	px.insert({ 0, x });
	set<pair<ll, int> > py;
	py.insert({ 0, y });
	set<pair<ll, int> > pxy; // vieme sa uz dostat z x sem, kolko musime zaplatit aby sa sem aj y vedelo dostat?
	set<pair<ll, int> > pyx;
	while (true)
	{
		ll now = min({ score(px), score(py), score(pxy), score(pyx) });
		if (now > k) break;
		k -= now;
		if (px.size() && px.begin()->first == now)
		{
			int u = px.begin()->second; px.erase(px.begin()), ansx[u] = 1;
			if (py.count({ cy[u], u })) py.erase({ cy[u], u }), pxy.insert({ cy[u] - cx[u], u });
			for (pair<int, int> i : g[u]) if (!ansx[i.first])
			{
				if (!ansy[i.first]) px.insert({ cx[i.first], i.first });
				else				px.insert({ cx[i.first] - cy[i.first], i.first});
			}
		}
		else if (py.size() && py.begin()->first == now)
		{
			int u = py.begin()->second; py.erase(py.begin()), ansy[u] = 1;
			if (px.count({ cy[u], u })) px.erase({ cy[u], u }), pyx.insert({ cy[u] - cx[u], u });
			for (pair<int, int> i : g[u]) if (!ansy[i.first])
			{
				if (!ansx[i.first]) py.insert({ cy[i.first], i.first });
				else				py.insert({ cy[i.first] - cx[i.first], i.first });
			}
		}
		else if (pyx.size() && pyx.begin()->first == now)
		{
			int u = pyx.begin()->second; pyx.erase(pyx.begin()), ansx[u] = 1;
			for (pair<int, int> i : g[u]) if (!ansx[i.first])
			{
				if (!ansy[i.first]) px.insert({ cx[i.first], i.first });
				else				px.insert({ cx[i.first] - cy[i.first], i.first });
			}
		}
		else if (pxy.size() && pxy.begin()->first == now)
		{
			int u = pxy.begin()->second; pxy.erase(pxy.begin()), ansy[u] = 1;
			for (pair<int, int> i : g[u]) if (!ansy[i.first])
			{
				if (!ansx[i.first]) py.insert({ cy[i.first], i.first });
				else				py.insert({ cy[i.first] - cx[i.first], i.first });
			}
		}
	}
	return count(ansx.begin(), ansx.end(), 1) + count(ansy.begin(), ansy.end(), 1);
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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