Submission #900174

#	Time	Username	Problem	Language	Result	Execution time	Memory
900174		subrat0018	Race (IOI11_race)	C++17	100 / 100	249 ms	57024 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define nline "\n"
using uint = unsigned int;
const int M = 1e9 + 7;
const int M2 = 998244353;
const int INF = 1e9;
const int N = 1e6 + 10;
const double Degree = 57.2958;



int n,k;
int sz[N];
bool dead[N];
int dist[N];
vector<pair<int, int>> g[N];
vector<int> temp;
void prep(int v,int d, int len, int par = -1)
{
    if(len > k)return;
    dist[len] = min(dist[len], d);
    temp.push_back(len);
    for(auto &val:g[v])
    {
        if(val.first == par || dead[val.first])continue;
        prep(val.first, d + 1, len + val.second, v);
    }
}

int func(int v, int d, int len, int par = -1)
{
    if(len > k)return INF;
    int ans = d + dist[k - len];
    for(auto &val:g[v])
    {
        if(val.first == par || dead[val.first])continue;
        ans = min(ans, func(val.first, d + 1, len + val.second, v));
    }
    return ans;
}

void dfs(int v, int par=-1)
{
    sz[v] = 1;
    for(auto &val:g[v])
    {
        if(val.first != par && !dead[val.first])
        {
            dfs(val.first, v);
            sz[v] += sz[val.first];
        }
    }
}
int find_centroid(int currSize, int v, int par = -1)
{
    for(auto &val:g[v])
        if(val.first != par && !dead[val.first] && 2 * sz[val.first] > currSize)
            return find_centroid(currSize, val.first, v);
    return v;
}

int decompose(int v)
{
    dfs(v);
    int centorid = find_centroid(sz[v], v);
    dead[centorid] = true;
    
    int ans = INF;
    temp.clear();
    dist[0] = 0;
    for(auto &val:g[centorid])
    {
        if(!dead[val.first])
        {
            ans = min(func(val.first, 1, val.second, centorid), ans);
            prep(val.first, 1, val.second, centorid);
        }
    }
    dist[0] = INF;
    // set<int> st(temp.begin(),temp.end());
    // temp.clear();
    // temp.assign(st.begin(),st.end());
    for(auto &val:temp)
        dist[val] = INF;
    for(auto &val:g[centorid])
        if(!dead[val.first])
            ans = min(ans, decompose(val.first));
    return ans;
}
int best_path(int nn, int K, int H[][2], int* L)
{
    n = nn;
    k = K;
    vector<pair<int, int>> arr;
    for(int i=0;i<N;i++)
        dist[i] = INF;
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        u = H[i][0];
        v = H[i][1];
        arr.push_back({u,v});
    }
    int ct = 0;
    for(auto &val:arr)
    {
        int w;
        w = L[ct++];
        g[val.first].push_back({val.second, w});
        g[val.second].push_back({val.first, w});
    }
    int ans = decompose(0);
    if(ans >= INF)
        return -1;
    else
        return ans;
}

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