Submission #49440

#	Time	Username	Problem	Language	Result	Execution time	Memory
49440		ho94949	Race (IOI11_race)	C++17	100 / 100	2712 ms	94096 KiB

race

#include "race.h"
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
const int MAXN = 202020;
const int MAXK = 1010101;

int N, K;
vector<pair<int, int> > conn[MAXN];
bool visit_centroid[MAXN];

//solve for one vertex
namespace solver
{

set<int> used;
map<int, int> V[MAXK];

//added color & weight
void dfs(int a, int pa, int c, int len, int depth)
{
    if(len>K) return;
    
    used.insert(len);
    if(V[len][c] == 0) V[len][c] = depth;
    else V[len][c] = min(V[len][c], depth);
    
    for(auto tmp: conn[a])
    {
        int x, w; tie(x, w) = tmp;
        if(visit_centroid[x] || x == pa) continue;
        dfs(x, a, c, len + w, depth+1);
    }
}

int solve(int a) 
{
    
    int tp = 0;
    for(auto tmp: conn[a])
    {
        int x, w; tie(x, w) = tmp;
        if(visit_centroid[x]) continue;
        dfs(x, a, ++tp, w, 1);
    }
    used.insert(0);
    V[0][-1] = 0;
    
    int ans = N;
    for(int x: used)
    {
        pair<int, int> min1(N, 0), min2(N, 0);
        for(auto y: V[x])
        {
            auto yrev = make_pair(y.second, y.first);
            if(min1 > yrev)
            {
                min2 = min1;
                min1 = yrev;
            }
            else if(min2 > yrev) min2 = yrev;
        }
        for(auto y: V[K-x])
        {
            if(y.first != min1.second)
                ans = min(ans, y.second+min1.first);
            if(y.first != min2.second)
                ans = min(ans, y.second+min2.first);
        }
    }
    
    //cleanup
    for(int x: used) V[x].clear();
    used.clear();
    
    return ans;
}


}

//context getting centroid
namespace centroid
{
int size[MAXN];
int max_subsize[MAXN];
vector<int> subtree;
void dfs(int a, int pa)
{
    subtree.push_back(a);
    size[a] = 1; max_subsize[a] = 0;
    for(auto tmp: conn[a])
    {
        int x, _; tie(x, _) = tmp;
        if(visit_centroid[x] || x == pa) continue;
        dfs(x, a);
        size[a] += size[x];
        max_subsize[a] = max(max_subsize[a], size[x]);
    }
}
int get_centroid(int x)
{
    subtree.clear();
    dfs(x, -1);
    int minv = subtree.size();
    int mini = -1;
    for(auto y: subtree)
    {
        int v = max((int)subtree.size()-size[y], max_subsize[y]);
        if(minv > v)
        {
            minv = v;
            mini = y;
        }
    }
    return mini;
}
}

int best_path(int _N, int _K, int H[][2], int L[])
{
    N = _N; K = _K;
    for(int i=0; i<N-1; ++i)
    {
        int s = H[i][0], e = H[i][1], x = L[i];
        conn[s].emplace_back(e, x);
        conn[e].emplace_back(s, x);
    }
    int ans = N;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty())
    {
        int v = centroid::get_centroid(Q.front()); Q.pop();
        ans = min(ans, solver::solve(v));
        visit_centroid[v] = true;
        for(auto x: conn[v])
            if(!visit_centroid[x.first])
                Q.push(x.first);
    }
    if(ans == N) ans = -1;
    return ans;
}

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