oj.uz

Submission #919701

# Submission time Handle Problem Language Result Execution time Memory
919701 2024-02-01T13:27:48 Z prvocislo Closing Time (IOI23_closing) C++17
8 / 100
 104 ms 34256 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 29524 KB Output is correct
2 Correct 99 ms 34256 KB Output is correct
3 Correct 47 ms 5560 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 600 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -