Submission #1105630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105630		anngela	Race (IOI11_race)	C++17	0 / 100	2 ms	8784 KiB

race

#include <algorithm>
#include <vector>
#include <map>
using namespace std;
using pii = pair<int, int>;

const int N = 200005, INF = 2e9 + 11;
int k;

vector<pii> adj[N];
int sz[N];
bool del[N];
int ans = INF;
vector<pii> dist;

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

    return sz[x];
}

int Centroid(int x, int size, int t = -1) {

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

void DfsDists(int x, int t, int we, int d) 
{
    if (we > k || d > ans) return;
    dist.emplace_back(we, d);

    for (auto [y, w] : adj[x])
    {    
		if (y == t || del[w]) continue;
        DfsDists(y, x, we + w, d + 1);
	}
}

void BuildCentroidTree(int x) 
{
    int cen = Centroid(x, Size(x));
    map<int, int> mp;  // mp[dist] = lung_min

    for (auto [y, w] : adj[cen]) 
    {
        if (del[y])  continue;
        DfsDists(y, cen, w, 1);
        
        for (auto [we, d] : dist) 
        {
	        if (mp.find(k - we) != mp.end()) 
		        ans = min(ans, mp[k - we] + d);
	        else if (we == k) 
		        ans = min(ans, d);
	    }

	    for (auto [we, d] : dist) 
	    {
	        if (mp.find(we) == mp.end()) 
		        mp[we] = d;
	        else 
		        mp[we] = min(mp[we], d);
	    }
	    dist.clear();
    }

    del[cen] = 1;
    for (auto [x, _] : adj[cen])
    {
        if (del[x]) continue;
        BuildCentroidTree(x);
	}
}

int best_path(int n, int k, int h[][2], int l[]) 
{
    ::k = k;
    for (int i = 0, x, y, w; i < n - 1; i++) 
    {
		x = h[i][0], y = h[i][1], w = l[i];
        adj[x].emplace_back(y, w);
        adj[y].emplace_back(x, w);
    }

    BuildCentroidTree(0);
    return ans == INF ? -1 : ans;
}

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