Submission #1289587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289587		anngela	경주 (Race) (IOI11_race)	C++20	100 / 100	244 ms	31912 KiB

race

// OK
// AC 228 ms
// O(NlogN)
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

const int N = 2e5+5, W = 1e6+5, inf = 1e9;
#define father_centroid -1
int n, k, sz[N];
int lmin[W], ans;
bool del[N];
vector<pair<int,int>> adj[N];

int Size(int x, int t = -1)
{
	sz[x] = 1;
	for (auto [y, _] : adj[x])
	{
		if (y == t || del[y]) continue;
		sz[x] += Size(y, x);
	}
	return sz[x];
}

int Centroid(int x, int size, int t = -1) // O(log(size))
{
	for (auto [y, _] : adj[x])
	{
		if (y == t || del[y]) continue;
		if (2 * sz[y] > size)
			return Centroid(y, size, x);
	}
	return x;
}

queue<int> q;
stack<pair<int, int>> path;

// parcurg numai subarborele centroidului cen (x)
// la terminarea fiecarul nod x (care nu e centroidul de plecare), plasez in stiva <distanta, h> fata de centroid
// Toate lanturile trebuie sa treaca prin centroid. La descoperirea lui x, utilizez lmin[k - we] obtinut fara participarea vreunui nod din subarborele cu rad in fiul curent al centroidului,
void Dfs(int x, int t, int we = 0, int d = 0)                                                                   // subarbore care il contine si pe x
{
	if (we > k || d > ans) return;
	                                  //      [k -  we]  +  we
	if (lmin[k - we] != inf)          // daca lantul merge: y -- centroid -- x
		ans = min(ans, lmin[k - we] + d);  // lanturi care traverseaza centroidul
    if (t != father_centroid)
    {
        q.push(we);          // salvez costul drumului (distanta) de la centroid pana in x
		path.emplace(we, d);
    }

	for (auto [y, w] : adj[x])
	{
		if (del[y] || y == t) continue;

		Dfs(y, x, we + w, d + 1);

		if (t == father_centroid)   // daca x este centroidul de plecare
		{              // inainte sa plec spre urmatorul fiu, golesc path si retin minimele adancimilor pt fiecare distanta/cost. lmin NU se actualizeaza pt oricare nod
			while (!path.empty())                       // ci numai cand se trece la urmatorul fiu al centroidului
			{                                           // lmin e numai  in raport cu  centroidul ? si dist e in raport cu centroidul
				auto [cost, h] = path.top();
				path.pop();
				lmin[cost] = min(lmin[cost], h); // doar lanturi care coboara din centroid ?
			}
		}
	}
}

void Decompose(int x)
{
	int cen = Centroid(x, Size(x));
	del[cen] = true;

	Dfs(cen, -1);
    while (!q.empty())
    {
        int cost = q.front();
        q.pop();
        lmin[cost] = inf;
    }

	for (auto [y, _] : adj[cen])
		if (!del[y])
			Decompose(y);
}

int best_path(int N, int K, int H[][2], int L[]) // prototipul este obligatoriu
{
	n = N, k = K;
	for (int i = 0; i < n-1; i++)
	{
		int x = H[i][0] + 1, y = H[i][1] + 1, w = L[i]; // renumerotare noduri de la 1
		adj[x].emplace_back(y, w);
		adj[y].emplace_back(x, w);
	}

	ans = inf;
	for(int i = 1; i <= k; i++)   // important! lmin[0] = 0
		lmin[i] = inf;

	Decompose(1);
	return ans == inf ? -1 : ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57